Как узнать основную операцию при расчете сложности во время выполнения?

Question

Я пытаюсь получить наихудший порядок сложности во время выполнения для пары созданных алгоритмов. Тем не менее, я столкнулся с проблемой, что я продолжаю стремиться выбрать неправильное или неправильное количество фундаментальных операций для алгоритма.

Мне кажется, что выбор фундаментальной операции - больше искусство, чем наука. Посмотрев в Google и прочитав мои текстовые поля, я все еще не нашел хорошего определения. До сих пор я определял его как «Операция, которая всегда происходит при выполнении алгоритмов», такая как сравнение или манипулирование массивом.

Но алгоритмы часто имеют много сравнений, которые всегда выполняются, поэтому какую операцию вы выбираете?

Answer 1

Даже практикующие теоретики сложности имеют разногласия по поводу такого рода вещей, поэтому последующее может быть немного субъективным: http://blog.computationalcomplexity.org/2009/05/shaving-logs-with-unit-cost.html

Целью записи big-O является обобщение эффективности алгоритма для читателя. В практическом контексте меня больше всего беспокоит, сколько тактов занимает алгоритм, предполагая, что константа big-O не является ни чрезвычайно малой, ни большой (и игнорируя эффекты иерархии памяти); это модель «удельная стоимость», на которую ссылаются в связанном посте.

Причина подсчета сравнений для алгоритмов сортировки заключается в том, что стоимость сравнения зависит от типа входных данных. Можно сказать, что алгоритм сортировки занимает O (c n log n) циклов, где c - это стоимость сравнения, но в этом случае проще подсчитывать сравнения вместо этого, потому что другой работой, выполняемой алгоритмом, является O (n log n). Существует алгоритм сортировки, который сортирует объединение n отсортированных массивов длины n за n ^ 2 log n шагов и n ^ 2 сравнений; здесь я ожидал бы, что число сравнений и вычислительные затраты будут указаны отдельно, потому что ни одно из них не обязательно доминирует над другим.

Answer 2

Я согласен в некоторой степени, что это искусство, поэтому вы всегда должны уточнить, когда пишете документацию и т. Д. Но обычно это «посещение» базовой структуры данных. Итак, как вы сказали, для массива это сравнение или своп, для хэш-карты это может быть ручная проверка ключа, для графа это посещение вершины или ребра и т. Д.

Answer 3

Несколько простое определение, которое я слышал:

Операция, которая выполняется как минимум столько раз, сколько любая другая операция в алгоритме.

Например, в алгоритме сортировки это, как правило, сравнение, а не присвоение, так как вам почти всегда приходится посещать и «проверять» элемент перед его повторным заказом, но проверка может не привести к повторному заказу. , Так что всегда будет как минимум столько же сравнений, сколько заданий.

Answer 4

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