анализ временной сложности моих программ

Question

У меня есть проблема в определении временных сложностей алгоритмов.

for(int i=0;i <n i++){}   O(n)

for(int i= 0 ;i<n ;i++){    O(n^2)
  for(int j=0;j<n;j++){ 

  }
}

Теперь для следующего кода, в чем сложность

for(i =0; i<n ; i++) {}
for (j=0;j<n ;j++ ) {} 

это O (2n), поскольку он задействует 2 отдельных цикла?

что, если я начну j =От 5 до n?

Answer 1

Нет O(2n), это просто O(n). Другими словами, он масштабируется с той же скоростью, что и n.

Если бы это был вложенный цикл , это был бы O(n<sup>2</sup>), но наличие ваших {} пустых блоков означает, что он не является вложенным.

И не имеет значения, начинаете ли вы с одного или пяти, оно все равно масштабируется с n, только с немного отрицательным постоянным сложением. Следовательно все еще O(n).

Сложности O(n), O(cn) и O(n+c) (где c - это константа) все эквивалентны. Кроме того, вы также обычно используете только термин с наибольшим эффектом.

Так что вы обычно не увидите O(7n<sup>3</sup> + 3n<sup>2</sup> + 12n + 2), которое будет упрощено до O(n<sup>3</sup>).

Answer 2

Есть два важных правила сложности Времени, которые применяются тогда и только тогда, когда значение n очень велико ...

1. Коэффициент коэффициента высшего порядка можно пренебречь.

2. Все члены более низкого порядка могут быть обозначены игрой.

Почему эти предположения довольно просты, давайте рассмотрим пример: -

Предположим, сложность по времени составляет 5n ^ 2 + 3n.При очень низких значениях n коэффициент и члены более низкого порядка становятся заметными при небольшом изменении n.Но предположим, что если значение n очень велико, влияние члена более низкого порядка на сложность времени будет намного меньше, и, кроме того, коэффициент члена более высокого порядка также можно игнорировать аналогичным образом.

Примечаниевременная сложность играет основную роль только тогда, когда n теоретически приближается к бесконечности.

Answer 3

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

Итак, по сути, O (2n) == O (n).

Answer 4

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

мои извинения, небольшая опечатка, основанная на неправильном прочтении последних строк кода.Тот, о котором вы спрашивали, был бы Big O (n)

Answer 5

Сложность - это измерение для формы функции, которая описывает отношение ввода n и времени.

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

Посмотрите на сложность таким образом.

Допустим, у вас есть алгоритм, который принимает n = миллион. Каков приблизительный размер или порядок количества операций

O(n)            -> 1e6   and this can be calculated in most cases  
O(n * log(n))   -> 2*1e7 this can also be calculated in reasonable time.
O(n^2)          -> 1e12  you will not be able to compute whit this algorithm in reasonable time
O(n^3)          -> 1e18  here are so many operations that you have to think twice on how you are going to aproach this problem

Answer 6

Да, это O (2n), но это то же самое, что O (n), потому что умножение на константу не имеет значения при асимптотической сложности. Точно так же, если вы пропустите пять первых элементов, ваш цикл займет время O (n-5), но это тоже самое, что O (n), потому что сложение или вычитание константы даже слабее, чем умножение на константу. Смотрите, например http://en.wikipedia.org/wiki/Big_O_notation для определений.