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

Прошло немного времени с тех пор, как я оценил большое обозначение O на что-то, и, похоже, я не могу справиться с этим. В основном мой сценарий проходит через список точек в США с широтой/долготой и находит набор, который охватывает страну, если эти точки являются центром кругов с радиусом 100 миль. Так как это:Чувствуете большое значение нотации для моего скрипта?

Начало цикла по списку, индекс = 0.
Найти расстояние между точкой-го в списке и во всех пунктах, которые следуют за ним в списке.
Удалите все точки, которые находятся в пределах 100 миль
Переиндексирования массива
Увеличение индекса на один
Если я = длина списка, конец, иначе, петля

источник

2013-10-11 Ian

Нам нужно будет увидеть ваш фактический код, чтобы определить фактический Big-O. – iamnotmaynard

Я не понимаю вашего алгоритма. Если ваша цель состоит в том, чтобы найти ** ** набор точек, почему вы их удаляете? Вы действительно ищете ** минимальный ** набор баллов, который охватывает страну? – John

Вопрос уже ответил, но я подумал, что стоит отметить, что худший случай для этого алгоритма - это когда ваши очки отсортированы (например, на восток-запад). –

Вы алгоритм O(N^2), где n. Если я правильно понял ваше описание правильно, это выглядит примерно так:

for point A in array: 
    for point B in array: 
     d = dist(A,B) 
     //optionally remove from list

В худшем случае, каждая пара точек более чем 100 миль друг от друга, так что вы в конечном итоге проверки расстояния между каждой парой, следовательно O(N^2).

Обратите внимание, что вы делаете не более n + (n-1) + (n-2) + ... + 2 + 1 = (n(n+1))/2 расчет расстояний, который по-прежнему O(N^2).

источник

2013-10-11 17:36:13 mbatchkarov

Скажем, n - это количество очков, которые у вас есть в качестве входных данных.

Начало цикла по списку, индекс = 0.

...

Если я = длина списка, конец, иначе, петля

Так вот n итераций.

Найти расстояние между i-й точкой в списке и всеми пунктами, которые следуют за ним в списке.

Это n операции за итерацию. Если бы это были только эти два, это заканчивалось n^2/2 (каждая точка с каждой другой точкой, кроме порядка, не имеет значения, поэтому вы делаете половину сравнений).

Удалите все точки, которые находятся в пределах 100 миль

Переиндексирования массив

Из того, что это звучит как, вы обнуление из тех элементов, которые находятся в пределах 100 миль, то переход массив. Оба являются O(n) операций, которые заканчиваются O(n^2), так как у вас есть операция O(n), повторенная n раз.

Итак, у вас есть O(n^2).

источник

2013-10-11 17:38:17 Claudiu

Я возражаю против вас, говоря: «O (n^2/2 + n^2)» является «более конкретным», чем «O (n^2)». Они такие же. У этого есть только куча тривиальных данных. Если вы хотите указать постоянные факторы, рассмотрите [тильда (~) нотация] (https://en.wikipedia.org/wiki/Big_O_notation#Family_of_Bachmann.E2.80.93Landau_notations). – Dukeling

@ Dukeling: это более конкретно, потому что, хотя заказ одинаков, он дает вам больше информации. Алгоритм, который является «O (14n)», по-прежнему в 7 раз медленнее, чем алгоритм, который является «O (2n)», хотя это не имеет значения для больших 'n'. Но для маленького 'n' это могло бы быть. Аналогично, если один алгоритм равен «O (43009n^2)», а другой - «O (n^3)», вы можете использовать 'O (n^3)' one, если ваш 'n' достаточно мал, но если вы видите просто 'O (n^2)' vs 'O (n^3)', у вас нет такой информации, чтобы принять это решение. – Claudiu

Но вы также можете сказать, что алгоритм, который выполняется 14 раз для каждого элемента, является 'O (2n)'. (И 'O (n^2)' в этом отношении, хотя здесь вы можете сказать, что «O (n)» является «более конкретным».) По определению, постоянные факторы и асимптотически меньшие члены ничего не означают в обозначениях большой O. Приписывание им какого-то значения является ошибочным. – Dukeling

выполнения вашего алгоритма O(n^2), а в худшем случае вы перебирать массив и проверить каждый пункт против всех следующих точек в массиве, таким образом n(n-1)/2 сравнения, который O(n^2)

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

источник

2013-10-11 17:38:39

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

ответ

Смежные вопросы