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

[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]

Специально для Lenochka. Детально и без размахивания регистрами ответить на ентот вопрос не смогу т. к. в универе не учился. Здесь нужно копать в том направлении, что сложность алгоритма ависит от скорости его выполнения, следовательно, чем больше в нём рекурсий (типа чем больше он тормозит) тем он сложнее. А чем он оптимизированнее тем менее сложен. Зайди на mail.ru и загони в поисковик фразу "нахождение сложности алгоритма"

[___ALex___]

SKVOZNJAK
тож ентим не занимался, но знаю что алгоритмы имеющие одинаковую сложность могут как угодно различаться по скорости работы, она показывает характер кривой в осях, к примеру, в случае сортировки - длина сортируемой последовательности, время сортировки
мадам, как в теории-то сложность ищется?мож эмпирически?

[exp]

Сложность алгоритма зависит от количества производимых операций, а от этого уже зависит время выполнения.

Причем важен порядок этого кол-ва элементов.
Думаю, понятно, что одно присваивае или любая другая операция,
количество выполнений которой не зависит от n, не может существенно повлиять на время выполнения при достаточно больших n.

В первой проге (процедура ANTYLEX):

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

Сложность O(n!) //a придется опредеоить самой
т.к. первый же проход цикла (i=1) вызовет за собой n! вызовов себя же.
В остальных прогах аналогично.

Да, если ты на первом курсе, то еще ладно, а вообще сложность любого ангоритма по нахождению перестановок элементов имеет сложность O(n!), так как всего перестановок сущ n!

И последнее: 1) бросай этот форум
2) переходи на C++
3) и не слушай тех, кто считает, что рекурсия замедляет программу и усложняет алгоритм. Вранье. Достаточно вспомнить сортировку Хоара.

Сообщение отредактировано: volvo - 17.12.2004 15:54

[exp]

Прошу прощения, за небольшую некорректность.

первый вызов процедуры вызовет за собой n  вызовов себя же.
Каждый из них вызовет своего "двойника" по n-1 раз и так далее => организуется процесс n*(n-1)*(n-2)*...*2. На единице все обрывается.
Теперь видно, что сложность действительно n!.

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

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

[SKVOZNJAK]

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

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

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

[SKVOZNJAK]

И последнее: 1) бросай этот форум
                      2) переходи на C++

PS. От СИонистов ничего другого и не ждали.  И не вы ли сами и являетесь Леночкой , и не сами ли отвечали на собственный вопрос?  ;)