Распространенные заблуждения о больших затратах и ​​алгоритмической сложности

Распространенные заблуждения о больших затратах и ​​алгоритмической сложности

Вы неправильно используете Big-O?

Big-O - это простое и очень общее понятие - количество примитивных операций, необходимых для завершения алгоритма с некоторым параметром n, - которое очень легко может быть истолковано как нечто, чем оно не является.

Распространенное заблуждение - использовать убедительную нотацию Big-O и рассматривать ее как функцию. Например, написав такое заявление:

Поскольку Big-O написан как функция, многие считают ее таковой. Однако это просто протокол нотации, и все термины в g (n), которые не являются «движущими силами», отбрасываются, чтобы описать общую форму среды выполнения как n масштабируется все выше и выше. Хотя всем известно, что Big-O - это не функция, этот тип мышления часто проявляется в замаскированной форме в других сценариях.

Например, такие вопросы, как «алгоритм - O (n ²). При n = 5 алгоритм занимает 10 секунд. Сколько времени займет выполнение алгоритма при n = 10? » основаны на предположении, что O (n ²) - это функция, и на другом заблуждении относительно взаимосвязи между временем и сложностью, что будет рассмотрено далее.

Другой пример: лежащее в основе убеждение, что Big-O - это функция, заставляет людей делать глупые сравнения между алгоритмами, заявляя, что один «лучше», чем другой, на основе «лучшей» формы Big-O. Например, рассмотрим два алгоритма: один с O (n ²), а другой с O (n ³). Для многих убедительно прямо установить, что первое в некотором роде «лучше», чем второе, просто из-за формы движущих сил, стоящих за сложностью масштабирования.

Хотя это, по общему признанию, несколько крайний пример, теперь переосмыслите свое сравнение: какой алгоритм «лучше»?

Более того, сравнение алгоритмов может вообще не быть оправданным, в зависимости от того, что означает n. Разные алгоритмы работают по-разному, поэтому иногда их вообще нельзя сравнивать. Например, рассмотрим сортировку слиянием с O (n log n), которая является частью семейства алгоритмов сортировки, основанных на сравнении, что означает сортировку элементов путем их сравнения. относительно других. Radixsort - O (n). Даже не принимая во внимание мультипликативные и аддитивные константы, справедливо ли сказать, что Radixsort имеет меньшую сложность, чем Mergesort? Нет!

Это связано с тем, что Radixsort не основан на сравнении, поскольку он никогда не сравнивает два ключа, а вместо этого основывает сортировку по разряду. n не означает одно и то же в Mergesort и Radixsort. Чтобы сравнить эти две сложности, мы должны определить общую модель вычислений, например, используя действие чтения байта как примитивную операцию.

С другой стороны, сравнение сложностей Mergesort с другим алгоритмом, основанным на сравнении, таким как Quicksort, было бы законным, если бы учитывались ограничения того, что означает Big-O.

Кроме того, существует большая путаница в том, что именно представляет собой Big-O и как его использовать. Хотя он строго определен как верхняя граница, он использовался для представления ожидаемого времени работы, нижних границ и целого ряда других целей. Если вы хотите быть математически точным, вы должны использовать следующее:

• Ω (g (x)) для нижней границы (большой омега).
• Θ (g (x)) для «точного» индикатора, то есть он ограничен как сверху, так и снизу с помощью g (x ) (большая тета).

С другой стороны, просто используя «верхняя граница O (m (x)), а нижняя граница - O (n ( x)) », чтобы избежать хлопот с поиском символов, как правило, также считается приемлемым, но важно указать роль, в которой используется Big-O. Ключ состоит в том, чтобы не забывать, что Big-O является частью широкого семейства нотаций об алгоритмической сложности и асимптотической нотации, и не позволять простоте набора текста влиять на то, как вы его используете.

Однако самым большим заблуждением является то, что Big-O каким-то образом является утверждением о времени, и что такой оператор, как O (n ³), означает, что время, необходимое для выполнения операции, кубизируется при каждом увеличении n (без учета, конечно, мультипликативных и аддитивных констант). Хотя в этом может быть доля правды, Big-O никогда не следует использовать для обозначения времени, необходимого для выполнения алгоритма.

Когда кто-то говорит, что временная сложность Mergesort равна O (n log n), они имеют в виду, что это делает n log n сравнения или примитивные операции для этого алгоритма (так как Mergesort запускается при сравнении). Не все алгоритмы подходят к своей задаче одинаково, даже если они используют одни и те же примитивные операции, и, следовательно, некоторые «операции с строительными блоками», такие как разбиение на разделы в Quicksort, могут выполняться на компьютере медленнее или быстрее.

Например, шаблоны доступа к памяти играют важную роль в фактическом времени работы алгоритма. Mergesort и Quicksort проходят через память более линейным образом и относительно более удобны для кешей и виртуальной памяти, чем алгоритмы вроде Heapsort. Этот алгоритм обрабатывается таким образом, что он перемещается по памяти почти случайным образом, вызывая промахи в кэше и сбои страниц. Однако и Heapsort, и Mergesort имеют сложность O (n log n).

В итоге:

• Big-O - это не функция, это упрощение, чтобы описать грубую движущую силу, стоящую за количеством необходимых примитивных операций.
• При сравнении сложности убедитесь, что алгоритмы используют одно и то же определение n и используют одни и те же примитивные операции. В противном случае даже тщательное сравнение сложности недействительно.
• Старайтесь не использовать и не интерпретировать Big-O как что-либо, кроме верхней границы, если не указан сопроводительный текст «нижняя граница…» или соответствующий символ.
• Big-O - это не утверждение о времени, и его не следует воспринимать как таковое. Фактическое время, необходимое для выполнения алгоритма, можно измерить путем его реализации.