Какой у меня Big O?

Question

Моя программа сортировки значений часов:

• 100000 8с
• 1000000 82 с
• 10000000 811

Это O (n)?

Answer 1

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

Answer 2

Да, для меня это выглядит как O (n) - переходя от 1-го к 2-му и от 2-го к 3-му, вы увеличили ввод в 10 раз, и он занял в 10 раз больше времени.

В частности, похоже, что вы можете предсказать приблизительное время, используя:

f(n) = n / 12500

или

f(n) = n * 0.00008

, который дает простейшее объяснение O (n) для предоставленных данных.

РЕДАКТИРОВАТЬ: Однако ... Как было указано, существуют различные способы, которыми данные могут вводить вас в заблуждение - мне скорее нравится идея Денниса Палмера, что стоимость ввода-вывода затмевает все остальное. Например, предположим, у вас есть алгоритм, абсолютное количество операций которого:

f(n) = 1000000000000n + (n^2)

В этом случае сложность по-прежнему равна O (n ^ 2), но это не станет очевидным из наблюдений, пока n не станет очень большим.

Я думаю, что было бы правильно сказать, что эти наблюдения наводят на мысль об алгоритме O (n) , но это не значит, что он определенно таков.

Answer 3

Поведение во времени не работает таким образом. Все, что вы действительно можете сказать, это то, что эти три набора данных примерно равны O (n) друг от друга. Это не значит, что алгоритм O (n).

Первая проблема заключается в том, что я мог бы легко нарисовать кривую, имеющую экспоненциальный характер (O (e ** n)), которая, тем не менее, включает эти три точки.

Большая проблема в том, что вы ничего не сказали о данных. Существует много алгоритмов сортировки, которые подходят к O (n) для отсортированных или почти отсортированных входных данных (например, Mergesort). Однако их средний случай (как правило, случайным образом упорядоченные данные) и наихудший случай (часто данные, отсортированные в обратном порядке) неизменно составляют O (nlogn) или хуже.

Answer 4

Вы не можете сказать.

Во-первых, время зависит от данных, среды и алгоритма. Если у вас есть массив нулей и вы пытаетесь его отсортировать, время выполнения программы не должно сильно отличаться для 1000 или 1000000 элементов.

Во-вторых, запись O говорит о поведении функции для большого значения n, начиная с n0. Может случиться так, что ваш алгоритм хорошо масштабируется до определенного размера ввода, а затем его поведение меняется - как функция g (n).

Answer 5

Вы не можете зависеть от того, чтобы сказать, что это O (n). Например, Bubblesort может выполнить n шагов, однако это алгоритм O (n ^ 2).

Answer 6

Да, это O (n), потому что оно масштабируется с количеством элементов.

1000000 = 10 * 100000

и

82s = 10 * 8s (roughly)

Answer 7

для меня это выглядит как O (n).

Answer 8

Да, похоже, это O (n), но я не думаю, что вы можете окончательно проанализировать алгоритм на основе его производительности по времени. Возможно, вы используете самый неэффективный алгоритм сортировки, но получите результаты по времени O (n), поскольку время чтения / записи данных составляет большую часть общего времени выполнения.

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