оценка временной сложности алгоритма, как это делать |
1. Заголовок или название темы должно быть информативным !
2. Все тексты фрагментов программ должны помещаться в теги [code] ... [/code] или [code=pas] ... [/code].
3. Прежде чем задавать вопрос, см. "FAQ" и используйте ПОИСК !
4. НЕ используйте форум для личного общения!
5. Самое главное - это раздел теоретический, т.е. никаких задач и программ (за исключением небольших фрагментов) - для этого есть отдельный раздел!
оценка временной сложности алгоритма, как это делать |
Айра |
11.03.2008 20:28
Сообщение
#1
|
Профи Группа: Пользователи Сообщений: 731 Пол: Женский Репутация: 25 |
Нужно оценить временную сложность алгоритма.. Например для этого кода:
program sort_par; Подскажите как это правильно сделать? Заранее, спасибо)) |
andriano |
11.03.2008 22:48
Сообщение
#2
|
Гуру Группа: Пользователи Сообщений: 1 168 Пол: Мужской Реальное имя: Сергей Андрианов Репутация: 28 |
O(n^2)
|
klem4 |
11.03.2008 22:53
Сообщение
#3
|
Perl. Just code it! Группа: Модераторы Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: 44 |
andriano, помоему вопрос был поставлен достаточно четко:
Цитата Подскажите как это правильно сделать? ?-------------------- perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
|
Айра |
11.03.2008 23:40
Сообщение
#4
|
Профи Группа: Пользователи Сообщений: 731 Пол: Женский Репутация: 25 |
у меня получилось, что в лучшем случае (массив уже отсортирован) - 2 (количество просмотров массива)
а в худшем (отсортирован в обратном порядке) n\2*(n+2), где n\2 - среднее количество сравнений (смущает меня эта переменная), а n+2 - кол-во просмотров.. Максимальная величина получается порядка О(n^2).. но по идее надо среднюю величину чтоли вычислять? |
andriano |
12.03.2008 8:27
Сообщение
#5
|
Гуру Группа: Пользователи Сообщений: 1 168 Пол: Мужской Реальное имя: Сергей Андрианов Репутация: 28 |
Насколько мне известно, оценка сложности основана на количестве операций, но не воспроизводит его один к одному.
Например, если количество операций 3(n-2)(n-1) + 7(n-2)(n-1)/(4n) + 16, то сложность оценивается как O(n^2), т.е. как все младшие степени, так и коэффициент при старшей опускаются. Кстати, в наилучшем случае сложность равна O(n), а не O(1). А оценка для среднего случая (именно она мной и приведена) совпадает с оценкой для наихудшего и составляет O(n^2). 2klem4: Русский язык допускает неоднозначность. И фраза "Как оценить" в большинстве случаев подразумевает не алгоритм оценки, а результат. Теперь по поводу алгоритма. Оценить, как всегда, можно аналитически и численно. Если бы это был алгоритм (где по-русски написано, что и ЗАЧЕМ делается), то разумнее было бы оценивать аналитически. Если же есть программа, то проще, естественно, оценить численно. В данном конкретном случае оценка проводилась по слегка измененной программе, приведенной ниже. Количество запусков - 5: при значениях n=1000, n=1000, n=1000, n=10000 и n=100000. Запуски 1-3 - чтобы оценить дисперсию, а 3-5 - сложность. Т.к. использовался random, то можно считать, что эта оценка относится к среднему значению. А оценка примерно такая: 0.45*n^2. Количество сортируемых чисел выбиралось из следующих соображений: - проводить оценку для единиц и десятков - бессмысленно, т.к. велика роль младших членов, поэтому 1000 - где-то минимально допустимое значение. - чтобы оценить динамику нужно не менее 3 точек, расположенных на одинаковом расстоянии по логарифмической шкале. - т.к. на глаз я оценил алгоритм как n^2, а мой опыт говорит, что такие алгоритмы уже при n=1000000 работают довольно долго, максимальное число составило 100000. В принципе, можно формализовать алгоритм определения сложности и написать программу, которая будет на выходе давать именно оценку сложности, т.е. одну из строк: "O(1)", "O(log(N))", "O(N)"... program sort_par; |
klem4 |
12.03.2008 14:59
Сообщение
#6
|
Perl. Just code it! Группа: Модераторы Сообщений: 4 100 Пол: Мужской Реальное имя: Андрей Репутация: 44 |
оффтоп
Цитата 2klem4: Русский язык допускает неоднозначность. И фраза "Как оценить" в большинстве случаев подразумевает не алгоритм оценки, а результат. Согласен, только в посте Айры такой фразы нет. -------------------- perl -e 'print for (map{chr(hex)}("4861707079204E6577205965617221"=~/(.{2})/g)), "\n";'
|
Айра |
12.03.2008 17:31
Сообщение
#7
|
Профи Группа: Пользователи Сообщений: 731 Пол: Женский Репутация: 25 |
в продолжение оффтопа: была фраза "как это сделать".. думаю она трактуется однозначно))))
и все таки, я не понимаю _как_ Мы посчитали количество сравнений, а затем поделили его на n^2.. почему надо делать именно так? Мне чет кажется, что надо умножать среднее количество сравнений на количество просмотров? А эти данные должны как-то получаться аналитически из кода.. исходя из количества элементов массива.. ..думаю мне нужен именно алгорит оценки (аналитический) на словах, на экзамене посчитать программно не получится.. |
andriano |
12.03.2008 20:09
Сообщение
#8
|
Гуру Группа: Пользователи Сообщений: 1 168 Пол: Мужской Реальное имя: Сергей Андрианов Репутация: 28 |
и все таки, я не понимаю _как_ Мы посчитали количество сравнений, а затем поделили его на n^2.. почему надо делать именно так? Исключительно для иллюстрации, что мы угадали.На самом деле можно написать программу, которая сама определяет, какой сложности алгоритм используется. В приведенном ниже примере подай на вход упорядоченную последовательность, например, так: for i:=1 to n[j] do b[i]:=i; для того, чтобы убедиться, что программа вернор определяет сложность хотя бы в этих двух (упорядоченный и не упорядоченный массив) случаях. program sort_par; Цитата ..думаю мне нужен именно алгорит оценки (аналитический) на словах, на экзамене посчитать программно не получится.. Возможно. Но тогда лучше и брать не исходный код на Паскале, а алгоритм, записанный по-русски, т.к. именно по-русски его и придется анализировать. Сообщение отредактировано: andriano - 12.03.2008 20:12 |
Айра |
21.03.2008 16:32
Сообщение
#9
|
Профи Группа: Пользователи Сообщений: 731 Пол: Женский Репутация: 25 |
Эх.. вернемся к нашим баранам..
Как оценивать временную сложность? (нужен алгоритм на словах..) Как глядя на код, не прибегая ни к каким дополнительным средствам оценить ее?.. |
Michael_Rybak |
21.03.2008 16:44
Сообщение
#10
|
Michael_Rybak Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
1) выделить переменные, относительно которых считается сложность
2) если два действия выполняются по очереди, берется максимум сложностей 3) если два действия выполняются одно внутри другого, сложности умножаются 4) числовые коэффициенты и свободные члены можно опускать 5) вообще, в многочлене можно оставлять старший член вообще, гораааздо легче на примерах. и показывать, и понимать. |
Айра |
21.03.2008 17:11
Сообщение
#11
|
Профи Группа: Пользователи Сообщений: 731 Пол: Женский Репутация: 25 |
Спасибо! А если в качестве примера взять ту сортировку, что в первом посте?
Сообщение отредактировано: Айра - 21.03.2008 17:13 |
Michael_Rybak |
21.03.2008 18:37
Сообщение
#12
|
Michael_Rybak Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
давай возьмем, давай
сразу разбиваем на последовательные блоки: блок номер раз: i:=0; блок номер два: for i:=1 to n do a[i]:=random(11)-5; блок номер три:
блок номер четыре: for i:=1 to n do write(a[i]:4); В блоке номер раз все выполняется за константное время. Константное относительно n. Смысл этой фразы в том, что при увеличении n время выполнения блока номер раз никак не увеличится. Таким образом, сложность первого куска равна O(1). Пишут единичку, потому что единичка никак не поменяется при увеличении n. В блоке номер два у нас циклы. Смотрим первый цикл. Одно действие (тело цикла) выполняется внутри другого (итерации цикла). Цикл выполняется n раз, значит сложность тела цикла нужно умножить на n. Как мы уже умеем определять, тело цикла имеет сложность O(1). Таким образом, сложность цикла - O(n). Второй цикл такой же. Сложность двух последовательных кусков, сложность каждого из которых равна O(n), тоже равна O(n). В блоке номер три у нас кривые руки. Мы зачем-то дико замаскировали самый банальный пузырек, проверяя то четные, то нечетные пары. Ну ок. Тут уже нужно включать аналитическую часть ума, и понимать, что в худшем случае вся эта байда (внешний while) выполнится n раз (можно оценивать и сложность в среднем, а не худшем случае, но исторически сложилось, что в computer science по умолчанию подразумевают сложность именно в худшем случае). Сложность тела while равна O(n), и таким образом, сложность третьего блока - O(n^2). Блок номер 4 у нас O(n). Таким образом имеем O(1), O(n), O(n^2) и O(n). Общая сложность O(n^2). Вообще, самый простой способ понять, что такое сложность - это функция, которая показывает, во сколько раз дольше будет работать программа, если размер входных данных увеличится во столько-то раз. К примеру, линейная сложность, O(n), означает, что если n будет в два раза больше, то и программа будет работать примерно в два раза больше. А сложность O(2^n) означает, что если n будет на 1 больше, программа будет работать на порядок дольше. Именно поэтому коэффициенты можно игнорировать. Конечно, всё это здесь неформально. На самом деле O(f(n)) - математический термин, и формулируется он в терминах пределов при n стремящемся к бесконечности. Но нам, нормальным людям, это ни к чему. |
andriano |
21.03.2008 18:39
Сообщение
#13
|
Гуру Группа: Пользователи Сообщений: 1 168 Пол: Мужской Реальное имя: Сергей Андрианов Репутация: 28 |
Конкретно в той сортировке есть два вложенных цикла while, откуда можно сделать вывод, что сложность не превышает O(N^2). Во внутреннем цикле перебор идет по i, причем i инкрементируется, т.е. сложность внутренего цикла O(N). Сложность внешнего цикла мне лично оценить труднее - ну не вижу я здесь явной переменной, по которой идет перебор, а комментарии, которые могли бы прояснить, что же автор этого кода хотел сказать, здесь почему-то отсутствуют. Но, в сущности, выбор невелик: это либо O(log(N)), либо O(N). При этом первый вариант менее вероятен, т.к. я нигде не увидел характерного для алгоритмов сложности O(log(N)) действия - деления интервала на 2 (бывает и по золотому сечению). Поэтому беглый осмотр приводит к выводу, что алгоритм похож на O(N^2).
Собственно, это предположение я и подтвердил программно (поэтому в моем первом исходнике я и делил на n^2). PS. Да, на остальные циклы можно внимания не обращать, т.к. у них сложность O(N). Сообщение отредактировано: andriano - 21.03.2008 18:40 |
Michael_Rybak |
21.03.2008 18:54
Сообщение
#14
|
Michael_Rybak Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
andriano, минимальным анализом там видно, что внешний цикл это просто условие "пока массив не отсортирован". это обычный пузырь.
|
andriano |
21.03.2008 21:48
Сообщение
#15
|
Гуру Группа: Пользователи Сообщений: 1 168 Пол: Мужской Реальное имя: Сергей Андрианов Репутация: 28 |
Ну не узнал я этого "простого пузыря" (и сейчас не узнаю), но по поведению (~(N^2)/2) очень похож.
|
Michael_Rybak |
21.03.2008 22:50
Сообщение
#16
|
Michael_Rybak Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Смотри, там l (маленькое L) - переменная, обозначающая, какие пары мы сейчас проверяем - четные, или нечетные.
Когда l = 1, проверяются пары элементов на позициях вида (2k + 1, 2k + 2). Когда l = 0 - позиции вида (2k, 2k + 1). Если в какой-то паре числа стоят в неправильном порядке (убывания) - числа в паре меняются местами, а счетчик l сбрасывается (опять начинаем с проверки пар вида (2k, 2k + 1)). Сообщение отредактировано: Michael_Rybak - 21.03.2008 22:53 |
Айра |
21.03.2008 23:07
Сообщение
#17
|
Профи Группа: Пользователи Сообщений: 731 Пол: Женский Репутация: 25 |
Цитата В блоке номер три у нас кривые руки У меня не кривые руки.. нам на лекциях эту сортировку дали.. Значит надо рассматривать именно худший вариант. И, в принципе, я поняла как это делать.. Спасибо большое!! [offtop] честно, я даже и не думала, что на этом форуме могут возникнуть проблемы с пониманием того, что происходит в конкретном коде [/offtop] Добавлено через 5 мин. Цитата там l (маленькое L) - переменная, обозначающая, какие пары мы сейчас проверяем - четные, или нечетные. Даже несколько проще (или просто другими словами))) l-ка увеличивается, когда нет замен, а если они есть, то сбрасывается.. даже в лучшем случае должно быть два просмотра, а тогда l будет равно 2.. |
andriano |
21.03.2008 23:14
Сообщение
#18
|
Гуру Группа: Пользователи Сообщений: 1 168 Пол: Мужской Реальное имя: Сергей Андрианов Репутация: 28 |
[offtop]Проблемы не с пониманием, проблемы с банальной ленью. [/offtop]
|
Michael_Rybak |
22.03.2008 3:10
Сообщение
#19
|
Michael_Rybak Группа: Модераторы Сообщений: 1 046 Пол: Мужской Реальное имя: Michael_Rybak Репутация: 32 |
Цитата У меня не кривые руки.. нам на лекциях эту сортировку дали.. Я рассчитывал на то, что ты поймешь, что я имею ввиду, что руки кривые - не у тебя, а у видного маскировщика пузырьковых сортировок, родившего сие (я почему-то верил, что это - не ты). Цитата Спасибо большое!! А вот всегда пожалуйста Цитата l-ка увеличивается, когда нет замен Это не другими словами, и не несколько проще - это разные аспекты. Я описал, в чем смысл переменной l, а ты - как он достигается. |
Айра |
22.03.2008 15:24
Сообщение
#20
|
Профи Группа: Пользователи Сообщений: 731 Пол: Женский Репутация: 25 |
Цитата Я описал, в чем смысл переменной l, а ты - как он достигается. Ой.. действительно разные вещи.. Цитата [offtop]Проблемы не с пониманием, проблемы с банальной ленью. sad.gif [/offtop] Хм.. а в чем она по твоему выражается?.. В том, что я не описываю алгоритм по вполне объяснимым причинам (1. на экзамене у меня будет только код, без словесного описания.. 2. я не думаю, что _здесь_ кто-то не может сам понять код), или кому-то просто лень самому подумать? Тем более, что такого сложного в этом коде, что его весь нужно комментировать?.. Сообщение отредактировано: Айра - 22.03.2008 15:24 |
Текстовая версия | 26.09.2024 19:39 |