Некоторые программисты умеют навскидку оценить сложность своего алгоритма в О-нотации, будь то C# или SQL. Как они это делают? Поделитесь источниками или объясните на пальцах. Спасибо.
-
1На самом деле вот так на вскидку, более чем уверен что оценить алгоритм нельзя. Например быстрая сортировка на 1 взгляд совсем не очевидна сложность. А в простейших вещах просто опыта достаточно, большинство "алгоритмов" оцениваются тупо по числу вложенных циклов. А вопрос слишком общий как по мне.– pavel19 фев 2017 в 6:57
-
1по базовой скорости роста трудоёмкости (к которой нужно привести алгоритм). Их там штук 8. Выбор в пользу меньшей.– Deadooshka19 фев 2017 в 7:32
-
Как оценивать по числу вложенных циклов?– Грузчик22 фев 2017 в 19:43
2 ответа
Какой вопрос - такой ответ... :)
Оценивается количество действий. Зачастую это приводит к некоторым рекуррентным соотношениям, которые в той или иной степени трудно решить - хотя имеются и готовые общие решения, так что оценить многие алгоритмы не так уж сложно.
Однако надо учитывать, что при оценке сложности алгоритма нужно рассматривать используемые структуры данных - например, в алгоритме Дейкстры многое зависит от того, как реализована очередь с приоритетами, да и вообще в алгоритмах на графах многое зависит от представления графа - списками смежности или матрицей...
В качестве простейшего примера - обычное перемножение матриц nxn
- каждый элемент новой матрицы получается путем перемножения и суммирования произведений элементов соответствующей строки и столбца. Длина строки/столбца - n
, итого, O(n)
операций для вычисления одного элемента результирующей матрицы. Всего их n
2 - итого, сложность алгоритма O(n
3)
.
Тема очень обширная, так что рекомендую обратиться к литературе, в особенности рекомендую Т. Кормен, Ч. Лейзерсон, Р. Ривест, К. Штайн - Алгоритмы. Построение и анализ. 3-е изд. - 2013.
-
Как-то можно привести упрощенную модель для оценки в уме сложностей, а именно способ составления приблизительной суперпозиции функций сложности для любой линейной программы? Кормена читать начал.– Грузчик22 фев 2017 в 19:45
-
Скажем так - я затрудняюсь ответить в общем виде. Обычно рассматриваются циклы, операции с памятью... Нет, не берусь ответить на ваш вопрос. Мне кажется, у вас это придет само - с опытом.– Harry22 фев 2017 в 20:09
-
1За Кормена смелый +1. Добавлю что сложность алгоритма стоит оценивать исходя из того что у Вас будет самый худший, просто самый ужасный набор данных для работы данного алгоритма, такой набор данных который потребует максимально возможное количество итераций. 1 мар 2017 в 11:48
Также как из другими "навскидку" оценками (основанными на интуиции), суть в уже усвоенном опыте: в доступности строительных блоков, которыми вы можете оперировать бессознательно в выбранной области, благодаря целенаправленной практике.
Большинство кода имеет простую алгоритмическую структуру. И если знать оценку для распространённых блоков (алгоритмов и операций над структурами данных в вашей области), то сложность кода очевидна. В C++ сложность для стандартных алгоритмов явно указана. Знание только к какой из трёх категорий ввод относится (случайный доступ/ RandomAccessIterator, последовательный/ForwardIterator, однопроходной/InputIterator) уже достаточно во многих случаях, чтобы оценить сложность алгоритма.
Можно даже не знать как что-то конкретно реализовано. К примеру, если алгоритм на каком-то шаге требует сортировки случайных данных, то разумно предположить O(n log n) для алгоритма, основанного на сравнениях, вне зависимости от конкретной реализации. Или при поиске в таблице в базе данных, если строк много (когда о big O имеет смысл говорить), можно ожидать что добротная реализация индекс создаст (поиск из O(n) в O(log n) превращается). В случае сомнений, можно измерить.
С другой стороны, даже внешне похожие простые примеры кода могут иметь отличающуюся сложность.
Чтобы найти или проверить интуитивный ответ, можно рекуррентные выражения или частичные суммы построить, которые с помощью компьютера вычислить. Так как есть O(c*n) == O(n)
и O(n*n + n) == O(n*n)
и другие упрощающие преобразования, то многие алгоритмы можно свести к небольшому числу базовых случаев. Процесс требует внимательности, но достаточно прямолинеен (особенно если задействовать что-нибудь вроде wolframalpha, Maple, Maxima, sympy). How to find time complexity of an algorithm.
Соответственно есть случаи, когда концентрированные усилия, используя очевидные подходы, результат не дают, тогда стоит отвлечься на какое-то время, переключиться на другие задачи. Озарение может прийти в самый неожиданный момент (но это уже за рамками "навскидку").
Посмотрите какие алгоритмы используются в задачах, которые вам интересны. Новые алгоритмы с лучшей сложностью не каждый день появляются.
Начните с самого простого кода на вашем языке, framework и узнайте его сложность (к примеру, "удаление по индексу элемента из массива"). Зная сложность для элементарных конструкций, найдите сложность для блоков кода (составленных из этих конструкций), с которыми вы часто встречаетесь.
Можно в обратную сторону: начать с более высокоуровневого кода и постепенно спускаться ниже по уровням абстракции, пока до известных блоков не дойдёте (сложение фиксированных чисел, которые в машинном слове помещаются: O(1). Если произвольное число n
взять, то O(log n) — пропорционально количеству бит в числе). См. таблицу сложностей по времени.
Практикуйтесь, пока большинство повседневного интересного вам кода не сможете навскидку оценить.
-
А где в документации пишут сложность операции в выбранном framework? Может, какие-то ключевые слова подскажете для поиска?– Грузчик22 фев 2017 в 19:46
-
1@ВладимирСмирнов: я сомневаюсь, что в большинстве framework вы прямо в документации найдёте подробный анализ временной сложности (time complexity) используемых алгоритмов (если это популярный язык, то можно ожидать, что временные сложности разумные, хотя конечно баги бывают. К примеру,
Array#reject!
в Ruby случайно имел квадратичную сложность, его документация ничего о сложности не говорит. Вот в ответе линейный алгоритм и объяснение почему линейность это желаемое свойство– jfs23 фев 2017 в 8:21