О, нет, еще один BigO один

Question

Я недавно делал BigO, и с формулой все в порядке, но я написал фрагмент кода, который принимает, вводит и возвращает время, необходимое для завершения сортировки. Итак, у меня есть вход и время, как я могу использовать это, чтобы классифицировать, что это за BigO? Я сделал графики и могу видеть, какие они есть, но я не могу сделать это по формуле? Я не силен в математике, которая, я думаю, моя проблема здесь!

Например, я получаю:

Size  Time    Operations
200    2     163648
400    1     162240
800    15    2489456
1600   6     10247376
3200   19    40858160
6400   79    165383984
12800  318   656588080
25600  1274  2624318128
51200  5059  10476803408
102400 20333 41969291968

Я знаю, что это O (n ^ 2), глядя на график и сравнивая, но как мне доказать это?

Answer 1

Да, вы можете выбрать тысячу различных входных размеров, а затем попытаться получить значение Big-O из этого, но вы не должны - не только потому, что это на самом деле ничего не доказывает, но потому что , чтоне в этом дело .

Способ доказать O (n ^ 2) состоит в том, чтобы доказать это на самом коде , а не путем экспериментов.Фактическое время выполнения не имеет значения, потому что нотация Big-O ничего об этом не говорит - в простых сроках она только определяет доминирующий член любой формулы, которую вы использовали бы для вычисления точного времени выполненияв смысле количества операций, выполненных для этой функции.Константы отбрасываются и поэтому являются более мелкими терминами - фактическое время выполнения функции может составлять 1000n ^ 2 + 1000000n, но это все равно O (n ^ 2).

Answer 2

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

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

То, что вы можете сделать, - это посмотреть на некоторые из ваших точек данных, чтобы получить поддержку для утверждения, что это O (n ² ). Посмотрите на последние четыре записи:

Input       Time
  128        318
  256       1274   1274 /  318 = 4.006
  512       5059   5059 / 1274 = 3.971
 1024      20333  20333 / 5059 = 4.019

Вы можете видеть, что каждое удвоение входного размера имеет эффект умножения времени около 4, что указывает на свойство O (n ² ).

Но это только поддержка. Он применяется только к этому конкретному диапазону входных значений и, как указано, зависит от факторов, находящихся вне вашего контроля. Также обратите внимание, что поддержку будет сложнее увидеть, если время не будет простым. Например, если бы функция времени была t = <sup>n<sup>2</sup></sup>/<sub>10</sub> + 123n + 123456789, было бы немного сложнее разобраться.

Answer 3

Вы не можете математически доказать что-либо из этой таблицы; сложность может быть O (1), если Time остается на 20333 для всех больших значений.

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

Answer 4

Простое сравнение значений может не иметь никакого смысла. Однако, если вы строите график, используя эти значения (ось X: вход, ось Y: время), вы получите кривую или линейную форму. или что угодно. Используя эту информацию, вы можете предсказать значение BigO этой функции. Конечно, могут быть (не всегда) некоторые прерывания, которые влияют на выполнение этого процесса, но это не длится в течение всего периода. Это небольшие накладные расходы. это не может повлиять на результат. Чтобы предсказать значение BigO, вам понадобятся некоторые знания Calculus, чтобы провести аналогию между формой и результатом BigO.

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

Есть некоторые другие функции, такие как Big-Theta, Small-Omega, которые связывают вашу функцию сверху или снизу. Математическая функция может быть обоими, но в результате ваша функция Big-O является ближайшей к эта форма.