IPB
ЛогинПароль:

> Прочтите прежде чем задавать вопрос!

1. Заголовок темы должен быть информативным. В противном случае тема удаляется ...
2. Все тексты программ должны помещаться в теги [code=pas] ... [/code], либо быть опубликованы на нашем PasteBin в режиме вечного хранения.
3. Прежде чем задавать вопрос, см. "FAQ", если там не нашли ответа, воспользуйтесь ПОИСКОМ, возможно такую задачу уже решали!
4. Не предлагайте свои решения на других языках, кроме Паскаля (исключение - только с согласия модератора).
5. НЕ используйте форум для личного общения, все что не относится к обсуждению темы - на PM!
6. Одна тема - один вопрос (задача)
7. Проверяйте программы перед тем, как разместить их на форуме!!!
8. Спрашивайте и отвечайте четко и по существу!!!

> Помогите студентке с нахождением сложности алгорит
сообщение
Сообщение #1


Гость






1. Генерирование всех последовательностейв антилексикографичеком порядке.Данные: n
Результат: Пеоследовательность перестановок множества {1,…,n} в антилексикографическом порядке.
(я очент извиняюсь, но сама прога написана на VB, но смысл тот же :smile.gif)
Цитата
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
 К началу страницы 
+ Ответить 
 
 Ответить  Открыть новую тему 
Ответов
сообщение
Сообщение #2


Гость






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

Причем важен порядок этого кол-ва элементов.
Думаю, понятно, что одно присваивае или любая другая операция,
количество выполнений которой не зависит от 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 -
 К началу страницы 
+ Ответить 

Сообщений в этой теме


 Ответить  Открыть новую тему 
1 чел. читают эту тему (гостей: 1, скрытых пользователей: 0)
Пользователей: 0

 





- Текстовая версия 29.03.2024 5:28
500Gb HDD, 6Gb RAM, 2 Cores, 7 EUR в месяц — такие хостинги правда бывают
Связь с администрацией: bu_gen в домене octagram.name