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


Профи
****

Группа: Пользователи
Сообщений: 930
Пол: Мужской

Репутация: -  11  +


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


Бывалый
***

Группа: Пользователи
Сообщений: 282

Репутация: -  0  +


SKVOZNJAK
тож ентим не занимался, но знаю что алгоритмы имеющие одинаковую сложность могут как угодно различаться по скорости работы, она показывает характер кривой в осях, к примеру, в случае сортировки - длина сортируемой последовательности, время сортировки
мадам, как в теории-то сложность ищется?мож эмпирически?
 Оффлайн  Профиль  PM 
 К началу страницы 
+ Ответить 
сообщение
Сообщение #4


Гость






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

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


Гость






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

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

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

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


Профи
****

Группа: Пользователи
Сообщений: 930
Пол: Мужской

Репутация: -  11  +


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

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


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


Профи
****

Группа: Пользователи
Сообщений: 930
Пол: Мужской

Репутация: -  11  +


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


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

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

 





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