Большая O путаница - PullRequest
Новая
       2

Большая O путаница

0 голосов
/ 24 декабря 2011

Я тестирую некоторые функции, которые я сделал, и пытаюсь выяснить сложность времени. Моя проблема в том, что даже после прочтения некоторых статей о Big O я не могу понять, что должно быть следующим:

1000 циклов: 15000 объектов: время 6

1000 петель: 30000 объектов: время 9

1000 петель: 60000 объектов: время 15

1000 циклов: 120000 объектов: время 75

Разница между первыми 2 составляет 3 мс, затем 6 мс, а затем 60, поэтому время увеличивается с каждой итерацией. Я знаю, что это не O (n), и я думаю, что это не O (log n).

Когда я пробую разные наборы данных, время не всегда увеличивается. Например, возьмем эту последовательность (мс): 11-17-26-90-78-173-300

78 мс выглядят неуместно. Это вообще возможно?

Edit: Н.В.М., мне просто нужно поговорить об этом с моим преподавателем в колледже. Выход времени слишком сильно отличается от разных переменных. Спасибо за тех, кто пытался помочь, хотя!

Ответы [ 3 ]

3 голосов
/ 24 декабря 2011

Обозначение Big O не о том, сколько именно времени требуется для завершения операции.Это (очень грубая) оценка того, как различные алгоритмы сравниваются асимптотически с изменением размеров входных данных, выраженных в общих «шагах».То есть «сколько шагов выполняет мой алгоритм для ввода N элементов?».

Сказав это, обратите внимание, что в обозначениях Big O константы игнорируются.Следовательно, цикл по N элементам, выполняющим 100 вычислений на каждой итерации, будет равен 100 * N, но все равно будет равен O (N).Точно так же цикл, выполняющий 10000 вычислений, все равно будет O (N).

Следовательно, в вашем примере, если у вас есть что-то вроде: 

for(int i = 0; i < 1000; i++)
   for(int j = 0; j < N; j++)
      // computations

, это будет 1000 * N = O (N).

Big O - это просто упрощенная оценка времени выполнения алгоритма, которая в основном говорит, что если у алгоритма есть время выполнения O (N), а у другого есть O (N ^ 2), то первый будет в конечном итоге будет быстрее второго для некоторого значения N. Эта оценка, конечно, не учитывает ничего, связанного с базовой платформой, например, скорость процессора, кеширование, узкие места ввода-вывода и т. Д.

0 голосов
/ 24 декабря 2011

Не видя вашего фактического алгоритма, я могу только догадываться: если вы разрешите постоянную инициализацию в 3 мс, вы получите 

1000x15,000 = (OH:3) + 3
1000x30,000 = (OH:3) + 6
1000x60,000 = (OH:3) + 12

Мне кажется, что это O (n)

Несоответствие в ваших временных метках разных наборов данных может быть вызвано любым количеством факторов.

0 голосов
/ 24 декабря 2011

Если вы не можете получить O (n) только из теории, тогда я думаю, что вам нужно просмотреть больше порядков в O (n) - как минимум три, предпочтительно шесть или более (вам просто нужно поэкспериментировать, чтобы увидеть, какое изменение в n требуется). Оставьте это на ночь, если нужно. Затем выведите результаты логарифмически.

По сути, я подозреваю, что вы сейчас смотрите на шум.

...