Форум программистов, компьютерный форум, киберфорум
Наши страницы
Алгоритмы
Войти
Регистрация
Восстановить пароль
 
 
Рейтинг 4.90/52: Рейтинг темы: голосов - 52, средняя оценка - 4.90
CyBOSSeR
Эксперт С++
2313 / 1686 / 148
Регистрация: 06.03.2009
Сообщений: 3,675
1

Оценка сложности алгоритма

13.03.2010, 20:29. Просмотров 9505. Ответов 22
Метки нет (Все метки)

Здравствуйте, уважаемые форумчане!
Появилась необходимость оценки временной сложности алгоритма (O(f(n))).
Вот таблица получившихся значений:

Количество входных данных .... Время выполнения
1.......................................... 1
2.......................................... 3
3.......................................... 6
4.......................................... 9
5.......................................... 15
6.......................................... 21
7.......................................... 28
8.......................................... 36
9.......................................... 45
10......................................... 55
11......................................... 66


Какова будет в данном случае порядковая оценка алгоритма?
0
Лучшие ответы (1)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
13.03.2010, 20:29
Ответы с готовыми решениями:

Оценка сложности алгоритма
1.for( i = 1 ; i < n ; i++){ }.. 2.for( i = 1 ; i <=n ; i++){ }.. 3....

Оценка сложности алгоритма
Подскажите какая сложность у данного алгоритма, искал в интернете что за...

Оценка сложности алгоритма!
пожалуйста выручите ) нужно оценить сложность алгоритма T(n)=3*(3/n)+n/log n

Оценка сложности небольшого алгоритма
s:=0; для i oт 1 до n нц для j от i-1 до i+1 нц s:= s + a кц кц

Оценка сложности алгоритма шифрования
Салют форумчане! Есть вопрос относительно оценки самопального алгоритма...

22
Mysterious Light
Эксперт по математике/физике
4079 / 1993 / 404
Регистрация: 19.07.2009
Сообщений: 3,009
Записей в блоге: 21
14.03.2010, 01:39 2
1. для 4 там точно 9? А то слишком уж на n*(n+1)/2 похоже.
2. из предыдущей формулы можно предположить ответ O(n^2)
2
CyBOSSeR
Эксперт С++
2313 / 1686 / 148
Регистрация: 06.03.2009
Сообщений: 3,675
14.03.2010, 01:55  [ТС] 3
Mysterious Light, все верно n*(n+1)/2 и есть.
Спасибо за ответ. Случайно не в курсе, если нормальная литература по оценки сложности алгоритма, без диких математических формул?
0
eugene0001
20 / 17 / 4
Регистрация: 07.02.2010
Сообщений: 59
15.03.2010, 02:10 4
блин,народ, строго измерять время выполнения алгоритма программно и потом делать вывод о сложности алгоритма - бред! Нужен разбор самого алгоритма аналитически...
0
Yurii_74
paladin
285 / 185 / 7
Регистрация: 25.02.2009
Сообщений: 592
15.03.2010, 07:00 5
Цитата Сообщение от eugene0001 Посмотреть сообщение
строго измерять время выполнения алгоритма программно и потом делать вывод о сложности алгоритма
Если из самого алгоритма известено только время на различных примерах, то вполне нормальный метод оценки сложности. В данном случае вообще прослеживается, как уже заметили, арифметическая прогрессия. Возможно, это всего лишь задачка по какому-то предмету. Бред - слишком неподходящее слово, в данном случае.
0
eugene0001
20 / 17 / 4
Регистрация: 07.02.2010
Сообщений: 59
16.03.2010, 02:06 6
ну вот ты сильно ошибаешься.
есть такие понятия, как время работы алгоритма в среднем,в худшем и наилучшем случаях.если для n мы подставим "лучшие" входные данные,а для n+1 подставим "средние" и т.д. по индукции,то сложность алгоритма не будет соответствовать времени.
если автор говорит на теорию алгоритмов "дикие математические формулы",то понятия о оценки сложности и их подходов не имеет.
0
Yurii_74
paladin
285 / 185 / 7
Регистрация: 25.02.2009
Сообщений: 592
16.03.2010, 07:59 7
Если считать, что оценки получены для каких-то случайных наборов тестов, то вполне можно сказать о средней сложности алгоритма. Без выяснения, что для лучших случаев будет что-то вида O(n), а для худших - O(n^3). В абсолютном большинстве алгоритмы работают на чем-то неопределенно среднем. Для специальных случаев придумывают и специальные алгоритмы.

Цитата Сообщение от eugene0001 Посмотреть сообщение
"дикие математические формулы"
неподготовленному человеку они именно так и представляются. Да и нужно ли это большинству, которое кроме +, -, /, * в своей жизни и не будет ничего использовать.
0
CyBOSSeR
Эксперт С++
2313 / 1686 / 148
Регистрация: 06.03.2009
Сообщений: 3,675
16.03.2010, 10:06  [ТС] 8
Цитата Сообщение от eugene0001 Посмотреть сообщение
если автор говорит на теорию алгоритмов "дикие математические формулы",то понятия о оценки сложности и их подходов не имеет.
Да, ты прав, не имею. И иметь дело с этим не хотелось бы вообще. Просто попался вопрос на собеседовании.

Да и для чего это прикладному программисту, которому все эти оценки сложности алгоритмов на фиг не сдались?
0
Yurii_74
paladin
285 / 185 / 7
Регистрация: 25.02.2009
Сообщений: 592
16.03.2010, 11:39 9
Цитата Сообщение от CyBOSSeR Посмотреть сообщение
прикладному программисту

Не по теме:

В какой области прикладываться требовалось? Разработка БД, алгоритмов? Или создание пользовательских междумордий?

0
CyBOSSeR
Эксперт С++
2313 / 1686 / 148
Регистрация: 06.03.2009
Сообщений: 3,675
16.03.2010, 12:26  [ТС] 10
Цитата Сообщение от Yurii_74 Посмотреть сообщение

Не по теме:

В какой области прикладываться требовалось? Разработка БД, алгоритмов? Или создание пользовательских междумордий?

На собеседовании требовалось оценить сложность предоставленного алгоритма и произвести его оптимизацию.
0
Genius Ignat
1245 / 783 / 108
Регистрация: 16.09.2009
Сообщений: 2,014
16.03.2010, 12:30 11
Yurii_74:
междумордий?
А перевод что это?
Это не в обиду мне? Я тоже прикладной программист.
0
CyBOSSeR
Эксперт С++
2313 / 1686 / 148
Регистрация: 06.03.2009
Сообщений: 3,675
16.03.2010, 12:36  [ТС] 12
Цитата Сообщение от Genius Ignat Посмотреть сообщение
Yurii_74:
междумордий?
А перевод что это?
GUI - графический интерфейс пользователя.
1
Genius Ignat
1245 / 783 / 108
Регистрация: 16.09.2009
Сообщений: 2,014
16.03.2010, 12:38 13
Присоединяюсь а автору темы, мне тоже интересно как оценить алгоритм...
0
Yurii_74
paladin
285 / 185 / 7
Регистрация: 25.02.2009
Сообщений: 592
16.03.2010, 14:31 14
Ну с оценкой сложности только по этим параметрам вроде как разобрались. А что оптимизировать-то? Или был сам текст проги?
0
CyBOSSeR
Эксперт С++
2313 / 1686 / 148
Регистрация: 06.03.2009
Сообщений: 3,675
16.03.2010, 17:04  [ТС] 15
Yurii_74, был исходный текст. Задача довольно таки тривиальная.
В прямоугольном поле, содержащем белые и черные клетки необходимо найти белый прямоугольник максимальной площади.
0
Yurii_74
17.03.2010, 07:35
  #16

Не по теме:

Ну для беглой оценки прогера этого хватит. Хотя первое задание сейчас должно быть примерно таким: "Напишите программу "Hello, World!" на требуемом ЯП"... дабы не задерживать претендентов с завышенной самооценкой :jokingly:

0
taras atavin
4206 / 1773 / 211
Регистрация: 24.11.2009
Сообщений: 27,565
17.03.2010, 08:05 17
Цитата Сообщение от Genius Ignat Посмотреть сообщение
А перевод что это
Вот тебе перевод:
Междумордие, междухаря, междурожа - грубые переводы слова interface на русский язык
.
0
CyBOSSeR
Эксперт С++
2313 / 1686 / 148
Регистрация: 06.03.2009
Сообщений: 3,675
19.03.2010, 01:09  [ТС] 18
Вопрос о литературе, посвященной оценке алгоритмов все еще остается открытым.
Может кто-то встречал стоящую книгу, желательно написанную программистом, а не математиком?

Добавлено через 6 часов 9 минут
В продолжении темы оценки алгоритма нахождения прямоугольника максимальной площади.

Если в худшем случае для поиска требуется h ((h + 1) / 2) + hw операций, где h – высота поля, w – ширина поля, то сложность данного алгоритма составляет O(n^2), где n - высота поля? Или я ошибаюсь?

Добавлено через 2 часа 12 минут
Вопрос актуален.
0
alex_x_x
бжни
2455 / 1662 / 134
Регистрация: 14.05.2009
Сообщений: 7,162
19.03.2010, 01:33 19
думаю О(h*(h+2w)/2)
могу соврать, но О (говориться о-большое) - некоторая величина, в данном случае величина сложности алгоритма, относительно действительной одного порядка, те

h ((h + 1) / 2) + hw = h( h + 2w + 1 )/2, эта величина одного порядка с h(h + 2w)/2
0
kazak
3061 / 2382 / 255
Регистрация: 11.03.2009
Сообщений: 5,438
Завершенные тесты: 1
19.03.2010, 03:46 20
Лучший ответ Сообщение было отмечено как решение

Решение

Теория алгоритмов - раздел математики, и стоящие книги по этой теме могут быть написаны только математиками ИМХО, так что Дональд Кнут "Искусство программирования".
3
19.03.2010, 03:46
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
19.03.2010, 03:46

Оценка сложности алгоритма на многомерном массиве
Где-то читал про правило, что количество вложенных циклов определяет сложность...

Оценка вычислительной сложности алгоритма [MatLab]
Всем привет! В общем вопрос может показаться легким, но к сожалению для меня он...

Оценка сложности алгоритма перемножение квадратной матрицы
Обычно один проход по одномерному массиву даст O(n). for (int i = 0; i <...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
20
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2019, vBulletin Solutions, Inc.
Рейтинг@Mail.ru