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

Question

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

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

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

Answer 1

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

Answer 2

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

Answer 3

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

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

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

Answer 4

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

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

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