#python #big-o #complexity-theory
#python #big-o #теория сложности
Вопрос:
Означает ли O (n ^ 2), что алгоритм будет выполнять цикл throw n ^ 2 раза?
for i in range(n):
for j in range(n):
print(1)
И тогда, если у меня есть код ниже O (n ^ 2 10), означает, что алгоритм будет выполнять цикл throw throw n ^ 2 10 раз?
for i in range(n):
for j in range(n):
print(1)
for i in range(10):
print(1)
Комментарии:
1. O (n ^ 2) означает алгоритм, который занимает в 4 раза больше времени при вдвое большем вводе. Это не точная мера того, сколько итераций вы делаете.
2. Простой вложенный цикл — это O (n ^ 2); Однако O (n ^ 2) не ограничивается простыми вложенными циклами. O(n ^ 2 10) — это то же самое, что и O (n ^ 2); члены более низкого порядка не имеют значения.
3. «Означает ли O (n ^ 2), что алгоритм выполнит цикл throw n ^ 2 раза?» Нет. «И тогда, если у меня есть код ниже O (n ^ 2 10), означает, что алгоритм выполнит цикл throw throw n ^ 2 10 раз?» Тоже нет. Вы можете начать читать en.m.wikipedia.org/wiki/Big_O_notation
Ответ №1:
Обычно вы смотрите на наихудшее или среднее время, затрачиваемое алгоритмом. Предоставленные вами алгоритмы в каждом случае выполняют ровно n ^ 2 и n ^ 2 10 шагов. Но некоторые алгоритмы имеют более сложные условия, когда это не так просто определить.
Нотация Big O была изобретена для ограничения времени выполнения алгоритма сверху. Обычно он анализируется для наихудшего времени выполнения. Идея заключается в том, что в основном имеют значение полиномиальные или экспоненциальные факторы, а константы не так важны. Хорошим примером являются приведенные вами примеры: вы можете сказать: f (n) = n ^ 2 10 = O(n ^ 2), потому что 10 не имеет значения, и именно n ^ 2 доминирует во время выполнения.
Ответ №2:
Двойной цикл должен содержать n чисел в первом цикле и n чисел во втором цикле, поэтому, как вы сказали, скорость равна O(n^2) . Однако 10 незначительно, но да O (n), что означает, что он линейный, скорость будет увеличиваться с увеличением n линейно. Не чем больше n растет, тем хуже становится