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

@CyBOSSeR · Регистрация: 06.03.2009

Author24 — интернет-сервис помощи студентам

Здравствуйте, уважаемые форумчане!
Появилась необходимость оценки временной сложности алгоритма (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

Какова будет в данном случае порядковая оценка алгоритма?

@Mysterious Light · 14.03.2010, 01:39

1. для 4 там точно 9? А то слишком уж на n*(n+1)/2 похоже.
2. из предыдущей формулы можно предположить ответ O(n^2)

@CyBOSSeR · 14.03.2010, 01:55 **[ТС]**

Mysterious Light, все верно n*(n+1)/2 и есть.
Спасибо за ответ. Случайно не в курсе, если нормальная литература по оценки сложности алгоритма, без диких математических формул?

@eugene0001 · 15.03.2010, 02:10

блин,народ, строго измерять время выполнения алгоритма программно и потом делать вывод о сложности алгоритма - бред! Нужен разбор самого алгоритма аналитически...

@Yurii_74 · 15.03.2010, 07:00

Сообщение от eugene0001

строго измерять время выполнения алгоритма программно и потом делать вывод о сложности алгоритма

Если из самого алгоритма известено только время на различных примерах, то вполне нормальный метод оценки сложности. В данном случае вообще прослеживается, как уже заметили, арифметическая прогрессия. Возможно, это всего лишь задачка по какому-то предмету. Бред - слишком неподходящее слово, в данном случае.

@eugene0001 · 16.03.2010, 02:06

ну вот ты сильно ошибаешься.
есть такие понятия, как время работы алгоритма в среднем,в худшем и наилучшем случаях.если для n мы подставим "лучшие" входные данные,а для n+1 подставим "средние" и т.д. по индукции,то сложность алгоритма не будет соответствовать времени.
если автор говорит на теорию алгоритмов "дикие математические формулы",то понятия о оценки сложности и их подходов не имеет.

@Yurii_74 · 16.03.2010, 07:59

Если считать, что оценки получены для каких-то случайных наборов тестов, то вполне можно сказать о средней сложности алгоритма. Без выяснения, что для лучших случаев будет что-то вида O(n), а для худших - O(n^3). В абсолютном большинстве алгоритмы работают на чем-то неопределенно среднем. Для специальных случаев придумывают и специальные алгоритмы.

Сообщение от eugene0001

"дикие математические формулы"

неподготовленному человеку они именно так и представляются. Да и нужно ли это большинству, которое кроме +, -, /, * в своей жизни и не будет ничего использовать.

@CyBOSSeR · 16.03.2010, 10:06 **[ТС]**

Сообщение от eugene0001

если автор говорит на теорию алгоритмов "дикие математические формулы",то понятия о оценки сложности и их подходов не имеет.

Да, ты прав, не имею. И иметь дело с этим не хотелось бы вообще. Просто попался вопрос на собеседовании.

Да и для чего это прикладному программисту, которому все эти оценки сложности алгоритмов на фиг не сдались?

@Yurii_74 · 16.03.2010, 11:39

Сообщение от CyBOSSeR

прикладному программисту

Не по теме:

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

@CyBOSSeR · 16.03.2010, 12:26 **[ТС]**

Сообщение от Yurii_74

Не по теме:

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

На собеседовании требовалось оценить сложность предоставленного алгоритма и произвести его оптимизацию.

@Ignat · 16.03.2010, 12:30

Yurii_74:
междумордий?
А перевод что это?
Это не в обиду мне? Я тоже прикладной программист.

@CyBOSSeR · 16.03.2010, 12:36 **[ТС]**

Сообщение от Genius Ignat

Yurii_74:
междумордий?
А перевод что это?

GUI - графический интерфейс пользователя.

@Ignat · 16.03.2010, 12:38

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

@Yurii_74 · 16.03.2010, 14:31

Ну с оценкой сложности только по этим параметрам вроде как разобрались. А что оптимизировать-то? Или был сам текст проги?

@CyBOSSeR · 16.03.2010, 17:04 **[ТС]**

Yurii_74, был исходный текст. Задача довольно таки тривиальная.
В прямоугольном поле, содержащем белые и черные клетки необходимо найти белый прямоугольник максимальной площади.

@Yurii_74 · 17.03.2010, 07:35

Не по теме:

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

@taras atavin · 17.03.2010, 08:05

Сообщение от Genius Ignat

А перевод что это

Вот тебе перевод:

Междумордие, междухаря, междурожа - грубые переводы слова interface на русский язык

.

@CyBOSSeR · 19.03.2010, 01:09 **[ТС]**

Вопрос о литературе, посвященной оценке алгоритмов все еще остается открытым.
Может кто-то встречал стоящую книгу, желательно написанную программистом, а не математиком?

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

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

Добавлено через 2 часа 12 минут
Вопрос актуален.

@alex_x_x · 19.03.2010, 01:33

думаю О(h*(h+2w)/2)
могу соврать, но О (говориться о-большое) - некоторая величина, в данном случае величина сложности алгоритма, относительно действительной одного порядка, те

h ((h + 1) / 2) + hw = h( h + 2w + 1 )/2, эта величина одного порядка с h(h + 2w)/2

@kazak · 19.03.2010, 03:46

Теория алгоритмов - раздел математики, и стоящие книги по этой теме могут быть написаны только математиками ИМХО, так что Дональд Кнут "Искусство программирования".

Новые блоги и статьи Все статьи Все блоги /
Вопросы на собеседованиях по микросервисам ArchitectMsa 27.03.2025 Работодатели ищут не просто разработчиков, знающих базовые концепции, а специалистов, разбирающихся в тонкостях масштабирования, отказоустойчивости и производительности. Сейчас на первый план выходят. . .	Взаимодействие Python с REST API py-thonny 27.03.2025 REST API - это архитектурный стиль взаимодействия компонентов распределённого приложения в сети. Python располагает функциональным набором инструментов для работы с REST API и основная библиотека для. . .	sshd restrictions, ssh access limitations jigi33 26.03.2025 sshd restrictions \| ssh access limitations рестрикции доступа на сервер sshd статья: https:/ / www. golinuxcloud. com/ restrict-allow-ssh-certain-users-groups-rhel	Компиляция C++ с Clang API NullReferenced 24.03.2025 Компиляторы обычно воспринимаются как черные ящики, которые превращают исходный код в исполняемые файлы. Мы запускаем компилятор командой в терминале, и вуаля — получаем бинарник. Но что если нужно. . .	Многопоточное программирование в C#: Класс Thread UnmanagedCoder 24.03.2025 Когда запускается приложение на компьютере, операционная система создаёт для него процесс - виртуальное адресное пространство. В C# этот процесс изначально получает один поток выполнения — главный. . .
SwiftUI Data Flow: Передача данных между представлениями mobDevWorks 23.03.2025 При первом знакомстве со SwiftUI кажется, что фреймворк предлагает избыточное количество механизмов для передачи данных: @State, @Binding, @StateObject, @ObservedObject, @EnvironmentObject и другие. . . .	Моки в Java: Сравниваем Mockito, EasyMock, JMockit Javaican 23.03.2025 Как протестировать класс, который зависит от других сложных компонентов, таких как базы данных, веб-сервисы или другие классы, с которыми и так непросто работать в тестовом окружении? Для этого и. . .	Архитектурные паттерны микросервисов: ТОП-10 шаблонов ArchitectMsa 22.03.2025 Популярность микросервисной архитектуры объясняется множеством важных преимуществ. К примеру, она позволяет командам разработчиков работать независимо друг от друга, используя различные технологии и. . .	Оптимизация рендеринга в Unity: Сортировка миллиона спрайтов GameUnited 22.03.2025 Помните, когда наличие сотни спрайтов в игре приводило к существенному падению производительности? Время таких ограничений уходит в прошлое. Сегодня геймдев сталкивается с задачами совершенно иного. . .	Образование и практика Igor3D 21.03.2025 Добрый день А вот каково качество/ эффективность ВУЗовского образования? Аналитическая геометрия изучается в первом семестре и считается довольно легким курсом, что вполне справедливо. Ну хорошо,. . .

@CyBOSSeR 2348 / 1721 / 149 Регистрация: 06.03.2009 Сообщений: 3,675

	Оценка сложности алгоритма 13.03.2010, 20:29. Показов 11496. Ответов 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

@Mysterious Light $Эксперт по математике/физике$ 4302 / 2093 / 431 Регистрация: 19.07.2009 Сообщений: 3,163 Записей в блоге: 24
	14.03.2010, 01:39
	1. для 4 там точно 9? А то слишком уж на n*(n+1)/2 похоже. 2. из предыдущей формулы можно предположить ответ O(n^2) 2

@CyBOSSeR 2348 / 1721 / 149 Регистрация: 06.03.2009 Сообщений: 3,675
	14.03.2010, 01:55 [ТС]
	Mysterious Light, все верно n(n+1)/2* и есть. Спасибо за ответ. Случайно не в курсе, если нормальная литература по оценки сложности алгоритма, без диких математических формул? 0

@eugene0001 21 / 18 / 4 Регистрация: 07.02.2010 Сообщений: 59
	15.03.2010, 02:10
	блин,народ, строго измерять время выполнения алгоритма программно и потом делать вывод о сложности алгоритма - бред! Нужен разбор самого алгоритма аналитически... 0

@Yurii_74 paladin 286 / 187 / 7 Регистрация: 25.02.2009 Сообщений: 589
	15.03.2010, 07:00
	Сообщение от eugene0001 строго измерять время выполнения алгоритма программно и потом делать вывод о сложности алгоритма Если из самого алгоритма известено только время на различных примерах, то вполне нормальный метод оценки сложности. В данном случае вообще прослеживается, как уже заметили, арифметическая прогрессия. Возможно, это всего лишь задачка по какому-то предмету. Бред - слишком неподходящее слово, в данном случае. 0

@eugene0001 21 / 18 / 4 Регистрация: 07.02.2010 Сообщений: 59
	16.03.2010, 02:06
	ну вот ты сильно ошибаешься. есть такие понятия, как время работы алгоритма в среднем,в худшем и наилучшем случаях.если для n мы подставим "лучшие" входные данные,а для n+1 подставим "средние" и т.д. по индукции,то сложность алгоритма не будет соответствовать времени. если автор говорит на теорию алгоритмов "дикие математические формулы",то понятия о оценки сложности и их подходов не имеет. 0

@Yurii_74 paladin 286 / 187 / 7 Регистрация: 25.02.2009 Сообщений: 589
	16.03.2010, 07:59
	Если считать, что оценки получены для каких-то случайных наборов тестов, то вполне можно сказать о средней сложности алгоритма. Без выяснения, что для лучших случаев будет что-то вида O(n), а для худших - O(n^3). В абсолютном большинстве алгоритмы работают на чем-то неопределенно среднем. Для специальных случаев придумывают и специальные алгоритмы. Сообщение от eugene0001 "дикие математические формулы" неподготовленному человеку они именно так и представляются. Да и нужно ли это большинству, которое кроме +, -, /, * в своей жизни и не будет ничего использовать. 0

@CyBOSSeR 2348 / 1721 / 149 Регистрация: 06.03.2009 Сообщений: 3,675
	16.03.2010, 10:06 [ТС]
	Сообщение от eugene0001 если автор говорит на теорию алгоритмов "дикие математические формулы",то понятия о оценки сложности и их подходов не имеет. Да, ты прав, не имею. И иметь дело с этим не хотелось бы вообще. Просто попался вопрос на собеседовании. Да и для чего это прикладному программисту, которому все эти оценки сложности алгоритмов на фиг не сдались? 0

@Yurii_74 paladin 286 / 187 / 7 Регистрация: 25.02.2009 Сообщений: 589
	16.03.2010, 11:39
	Сообщение от CyBOSSeR прикладному программисту Не по теме: В какой области прикладываться требовалось? Разработка БД, алгоритмов? Или создание пользовательских междумордий? 0

@CyBOSSeR 2348 / 1721 / 149 Регистрация: 06.03.2009 Сообщений: 3,675
	16.03.2010, 12:26 [ТС]
	Сообщение от Yurii_74 Не по теме: В какой области прикладываться требовалось? Разработка БД, алгоритмов? Или создание пользовательских междумордий? На собеседовании требовалось оценить сложность предоставленного алгоритма и произвести его оптимизацию. 0

Опции темы

@Ignat 1261 / 799 / 108 Регистрация: 16.09.2009 Сообщений: 2,010
	16.03.2010, 12:30
	Yurii_74: междумордий? А перевод что это? Это не в обиду мне? Я тоже прикладной программист. 0

@CyBOSSeR 2348 / 1721 / 149 Регистрация: 06.03.2009 Сообщений: 3,675
	16.03.2010, 12:36 [ТС]
	Сообщение от Genius Ignat Yurii_74: междумордий? А перевод что это? GUI - графический интерфейс пользователя. 1

@Ignat 1261 / 799 / 108 Регистрация: 16.09.2009 Сообщений: 2,010
	16.03.2010, 12:38
	Присоединяюсь а автору темы, мне тоже интересно как оценить алгоритм... 0

@Yurii_74 paladin 286 / 187 / 7 Регистрация: 25.02.2009 Сообщений: 589
	16.03.2010, 14:31
	Ну с оценкой сложности только по этим параметрам вроде как разобрались. А что оптимизировать-то? Или был сам текст проги? 0

@CyBOSSeR 2348 / 1721 / 149 Регистрация: 06.03.2009 Сообщений: 3,675
	16.03.2010, 17:04 [ТС]
	Yurii_74, был исходный текст. Задача довольно таки тривиальная. В прямоугольном поле, содержащем белые и черные клетки необходимо найти белый прямоугольник максимальной площади. 0

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

@taras atavin 4226 / 1796 / 211 Регистрация: 24.11.2009 Сообщений: 27,562
	17.03.2010, 08:05
	Сообщение от Genius Ignat А перевод что это Вот тебе перевод: Междумордие, междухаря, междурожа - грубые переводы слова interface на русский язык . 0

@CyBOSSeR 2348 / 1721 / 149 Регистрация: 06.03.2009 Сообщений: 3,675
	19.03.2010, 01:09 [ТС]
	Вопрос о литературе, посвященной оценке алгоритмов все еще остается открытым. Может кто-то встречал стоящую книгу, желательно написанную программистом, а не математиком? Добавлено через 6 часов 9 минут В продолжении темы оценки алгоритма нахождения прямоугольника максимальной площади. Если в худшем случае для поиска требуется h ((h + 1) / 2) + hw операций, где h – высота поля, w – ширина поля, то сложность данного алгоритма составляет O(n^2), где n - высота поля? Или я ошибаюсь? Добавлено через 2 часа 12 минут Вопрос актуален. 0

@alex_x_x бжни 2473 / 1684 / 135 Регистрация: 14.05.2009 Сообщений: 7,162
	19.03.2010, 01:33
	думаю О(h*(h+2w)/2) могу соврать, но О (говориться о-большое) - некоторая величина, в данном случае величина сложности алгоритма, относительно действительной одного порядка, те h ((h + 1) / 2) + hw = h( h + 2w + 1 )/2, эта величина одного порядка с h(h + 2w)/2 0

@kazak 3576 / 2721 / 350 Регистрация: 11.03.2009 Сообщений: 6,264
	19.03.2010, 03:46
	Сообщение было отмечено как решение Решение Теория алгоритмов - раздел математики, и стоящие книги по этой теме могут быть написаны только математиками ИМХО, так что Дональд Кнут "Искусство программирования". 3

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

Решение