Помогите студентке с нахождением сложности алгорит Опции

[Minx]

1. Генерирование всех последовательностейв антилексикографичеком порядке.Данные: n
Результат: Пеоследовательность перестановок множества {1,…,n} в антилексикографическом порядке.
(я очент извиняюсь, но сама прога написана на VB, но смысл тот же :)

Private Sub REVERSE(m As Integer)
Dim i, j, tmp As Integer
    i = 1
    j = m
    While i < j
        tmp = P(i)
        P(i) = P(j)
        P(j) = tmp
        i = i + 1
        j = j - 1
    Wend
End Sub
----------------------------------------------------
Private Sub ANTYLEX(m As Integer)
Dim i, tmp, k As Integer
Dim A As String

    If m = 1 Then
            A = ""
            For k = 1 To n
                A = A + Str(P(k))
            Next k
            lstAntylex.AddItem A
     Else
            For i = 1 To m
                  ANTYLEX (m - 1)
            If i < m Then
                            tmp = P(i)
                P(i) = P(m)
                      P(m) = tmp
               REVERSE (m - 1)
                  End If
Next i
     End If
End Sub
----------------------------------------------------
Private Sub cmdBegin_Click()  ' вводится число n заполняется массив начальными значениями,
    lstAntylex.Clear              '  последовательность будет выводится в ListBox - lstAntylex     
    n = txtN.Text
    ReDim P(n)
   
    For i = 1 To n
        tmp = P(i)
        P(i) = i
        i = tmp
    Next
ANTYLEX (n)
End Sub

2.Генерирование всех перестановок за минимальное число транспозиций.

Function B(m As Integer, j As Integer) As Integer
Dim tmp As Integer
   
    If (m Mod 2 = 0) And (m > 2) Then
        If j < m - 1 Then B = j Else B = m - 2
    Else
        B = m - 1
    End If
End Function
------------------------------------------------------------
Private Sub PERM(m As Integer)
Dim tmp, k, i As Integer
Dim A As String

    If m = 1 Then
            A = ""
            For k = 1 To n
                A = A + Str(P(k))
            Next k
            lstAntylex.AddItem A
    Else
        For i = 1 To m
            PERM (m - 1)
            If i < m Then
                tmp = P(B(m, i))
                P(B(m, i)) = P(m)
                P(m) = tmp
            End If
        Next i
     End If
       End Sub
------------------------------------------------------------
Private Sub cmdBegin_Click()
    lstAntylex.Clear
    n = txtN.Text
    ReDim P(n)
   
    For i = 1 To n
        tmp = P(i)
        P(i) = i
        i = tmp
    Next
    PERM (n)
End Sub

3.Генерирование всех перестановок с минимальным числом транспозиций соседних элементов.

Private Sub cmdBegin_Click()
Dim i, k, tmp, j As Integer

    lstAntylex.Clear
    n = txtN.Text
    ReDim P(n), C(n), PR(n)

    For i = 1 To n
        P(i) = i
       C(i) = 1
       PR(i) = True
    Next i
    C(n) = 0
    A = ""
    For j = 1 To n
        A = A + Str(P(j))
    Next j
   lstAntylex.AddItem A
    i = 1
    While i < n
     m = m + 1
        i = 1
        x = 0
        While C(i) = n - i + 1
            If PR(i) = True Then PR(i) = False Else PR(i) = True
            C(i) = 1
            If PR(i) Then x = x + 1
            i = i + 1
        Wend

        If i < n Then
            If PR(i) Then k = C(i) + x Else k = n - i + 1 - C(i) + x
            tmp = P(k)
            P(k) = P(k + 1)
            P(k + 1) = tmp
                A = ""
                For j = 1 To n
                    A = A + Str(P(j))
                Next j
               lstAntylex.AddItem A
            C(i) = C(i) + 1
        End If
    Wend
End Sub

[SKVOZNJAK]

П
Весьма развеселило мнение уважаемого SKVOZNJAK'а :
"Здесь нужно копать в том направлении, что сложность алгоритма ависит от скорости его выполнения, следовательно, чем больше в нём рекурсий (типа чем больше он тормозит  ) тем он сложнее. А чем он оптимизированнее тем менее сложен."

Получается, один и тот же алгоритм, выполненный на 2 GHz (т.е быстрее) и на 50 MHZ. Должен различаться по сложности.  :)
На 50 MHz алгоритм должен выглядеть сложнее (ведь он отработает дольше), а на  2GHz, естественно, этот же алгоритм уменьшит свою сложность, т.к отработал быстрее.
Забавная логика? Не так ли?  ;D

Логика конечно забавная  ;)  И она была-бы верна, если бы СКВОЗНЯК давал полный и развёрнутый ответ, а не подсказку, по каким дебрям поисковика лучше бродить чтобы сэкономить время и силы. В тех статьях, которые он там нашёл, про тактовую частоту также говорилось. Но нетрудно догадаться, что при увеличении ответа ещё на несколько десятков байт, последний уже претендовал-бы на развёрнутый. Что повлекло-бы за собой необходимость в дальнейшем изучением отвечающим данного материала Но ведь изучать его в такой мере было нужно не СКВОЗНЯКУ! И где же тут логика  :D  Кстати, о мегагерцах (про них в тех статьях тоже писалось, хотя правильнее было бы говорить об эффективной мощности проца, если склероз мне не изменяет...). Увеличение тактовой частоты необязательно приводит к ускорению выполнения конкретной проги. А последние выполняются, увы, не на процессорах, а на компьютерах   Далеко не каждый комп способен выделить под каждую прогу персональный процессор.  И здесь первостепенное имеют значение выделяемые для конкретной проги мощности, а уж откуда они берутся, дело десятое. И если на четвёртом пне тормозит винда (для этого необходимо выполнить всего-лишь 4 короткие зацикленные проги - для ХР), то и на четвёрке(вообще без винды) , прога ,возможно, выполнится скорее. Но это если придираться к буквам. Отрадно заметить, что после моего неполного ответа нашлись (на что я и расчитывал, по приколу) добры молодцы и включились в интеллектуальный поединок. Хотя некоторым участникам и пришлось неделю копить на это силы. Но за-то результат на лицо, но успела-ли ложка к обеду?