Версия для печати темы
Нажмите сюда для просмотра этой темы в обычном формате
Форум «Всё о Паскале» _ Задачи _ Помогите студентке с нахождением сложности алгорит
Автор: Minx 10.11.2003 16:53
1. Генерирование всех последовательностейв антилексикографичеком порядке.Данные: n
Результат: Пеоследовательность перестановок множества {1,…,n} в антилексикографическом порядке.
(я очент извиняюсь, но сама прога написана на VB, но смысл тот же :
)
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.Генерирование всех перестановок за минимальное число транспозиций.
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.Генерирование всех перестановок с минимальным числом транспозиций соседних элементов.
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 12.11.2003 12:44
Специально для Lenochka. Детально и без размахивания регистрами ответить на ентот вопрос не смогу т. к. в универе не учился. Здесь нужно копать в том направлении, что сложность алгоритма ависит от скорости его выполнения, следовательно, чем больше в нём рекурсий (типа чем больше он тормозит) тем он сложнее. А чем он оптимизированнее тем менее сложен. Зайди на mail.ru и загони в поисковик фразу "нахождение сложности алгоритма"
Автор: ___ALex___ 12.11.2003 12:52
SKVOZNJAK
тож ентим не занимался, но знаю что алгоритмы имеющие одинаковую сложность могут как угодно различаться по скорости работы, она показывает характер кривой в осях, к примеру, в случае сортировки - длина сортируемой последовательности, время сортировки
мадам, как в теории-то сложность ищется?мож эмпирически?
Автор: exp 20.11.2003 2:53
Сложность алгоритма зависит от количества производимых операций, а от этого уже зависит время выполнения.
Причем важен порядок этого кол-ва элементов.
Думаю, понятно, что одно присваивае или любая другая операция,
количество выполнений которой не зависит от n, не может существенно повлиять на время выполнения при достаточно больших n.
В первой проге (процедура ANTYLEX):
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) и не слушай тех, кто считает, что рекурсия замедляет программу и усложняет алгоритм. Вранье. Достаточно вспомнить сортировку Хоара.
Автор: exp 20.11.2003 3:57
Прошу прощения, за небольшую некорректность.
первый вызов процедуры вызовет за собой n вызовов себя же.
Каждый из них вызовет своего "двойника" по n-1 раз и так далее => организуется процесс n*(n-1)*(n-2)*...*2. На единице все обрывается.
Теперь видно, что сложность действительно n!.
Весьма развеселило мнение уважаемого SKVOZNJAK'а :
"Здесь нужно копать в том направлении, что сложность алгоритма ависит от скорости его выполнения, следовательно, чем больше в нём рекурсий (типа чем больше он тормозит ) тем он сложнее. А чем он оптимизированнее тем менее сложен."
Получается, один и тот же алгоритм, выполненный на 2 GHz (т.е быстрее) и на 50 MHZ. Должен различаться по сложности. :)
На 50 MHz алгоритм должен выглядеть сложнее (ведь он отработает дольше), а на 2GHz, естественно, этот же алгоритм уменьшит свою сложность, т.к отработал быстрее.
Забавная логика? Не так ли? ;D
Автор: SKVOZNJAK 21.11.2003 2:25
Весьма развеселило мнение уважаемого SKVOZNJAK'а :
"Здесь нужно копать в том направлении, что сложность алгоритма ависит от скорости его выполнения, следовательно, чем больше в нём рекурсий (типа чем больше он тормозит ) тем он сложнее. А чем он оптимизированнее тем менее сложен."
Получается, один и тот же алгоритм, выполненный на 2 GHz (т.е быстрее) и на 50 MHZ. Должен различаться по сложности. :)
На 50 MHz алгоритм должен выглядеть сложнее (ведь он отработает дольше), а на 2GHz, естественно, этот же алгоритм уменьшит свою сложность, т.к отработал быстрее.
Забавная логика? Не так ли? ;D
Логика конечно забавная ;) И она была-бы верна, если бы СКВОЗНЯК давал полный и развёрнутый ответ, а не подсказку, по каким дебрям поисковика лучше бродить чтобы сэкономить время и силы. В тех статьях, которые он там нашёл, про тактовую частоту также говорилось. Но нетрудно догадаться, что при увеличении ответа ещё на несколько десятков байт, последний уже претендовал-бы на развёрнутый. Что повлекло-бы за собой необходимость в дальнейшем изучением отвечающим данного материала
Но ведь изучать его в такой мере было нужно не СКВОЗНЯКУ! И где же тут логика :D Кстати, о мегагерцах (про них в тех статьях тоже писалось, хотя правильнее было бы говорить об эффективной мощности проца, если склероз мне не изменяет...). Увеличение тактовой частоты необязательно приводит к ускорению выполнения конкретной проги. А последние выполняются, увы, не на процессорах, а на компьютерах Далеко не каждый комп способен выделить под каждую прогу персональный процессор. И здесь первостепенное имеют значение выделяемые для конкретной проги мощности, а уж откуда они берутся, дело десятое. И если на четвёртом пне тормозит винда (для этого необходимо выполнить всего-лишь 4 короткие зацикленные проги - для ХР), то и на четвёрке(вообще без винды) , прога ,возможно, выполнится скорее. Но это если придираться к буквам. Отрадно заметить, что после моего неполного ответа нашлись (на что я и расчитывал, по приколу) добры молодцы и включились в интеллектуальный поединок. Хотя некоторым участникам и пришлось неделю копить на это силы. Но за-то результат на лицо, но успела-ли ложка к обеду?
Автор: SKVOZNJAK 21.11.2003 2:42
2) переходи на C++
PS. От СИонистов ничего другого и не ждали. И не вы ли сами и являетесь Леночкой , и не сами ли отвечали на собственный вопрос? ;)