Сложность вычислительного алгоритма - путаница

Question

У меня есть следующий фрагмент кода:

sum = 0;
for (i = 0; i < n; i++)
    for (j = 0; j < i; j++)
        sum++;

Сложность будет O(n^2), но если я захочу еще немного покопаться для сложности внутреннего цикла, то будет ли (n (n-1))/2 или (n-1)!?

Answer 1

Да, O (n ^ 2), но на самом деле 0 + 1 + ... + n-1 = n (n-1) / 2 = O (n ^ 2), определенно нет (n-1)!

Answer 2

time = n*(n-1)/2
     = (n*n - n)/2

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

Answer 3

Вы могли бы иметь алгоритм, который работает во времени

22222222222222 + 4444444444444*n + 9999999999999999999999999*n^2 steps

И это все равно будет O (n ^ 2).

Открытая проблема - найти лучшее описание времени работы алгоритма, чем O.

Answer 4

Прежде всего, (n-1)! означает (n-1)(n-2)...(2)(1). Это явно не то, что вы хотите здесь.

Если вы посчитаете фактическое количество итераций, то это будет 0 + 1 + 2 + ... + (n-2) + (n-1). Обратите внимание, что в сумме есть n слагаемых, и мы можем объединить их таким образом, чтобы среднее значение каждой пары было (n-1)/2. (Соедините самый высокий и самый низкий, второй самый высокий и второй самый низкий и т. Д.) Если n нечетно, у вас будет один оставшийся, который не может быть спарен, но для удобства его значение также равно (n-1)/2. Таким образом, у вас есть n терминов, а среднее значение для всех терминов составляет (n-1)/2, поэтому общая сумма составляет n(n-1)/2.

Теперь для больших O-нотаций не имеет значения, сколько именно у нас итераций - мы просто хотим знать предел, когда n очень велик. Обратите внимание, что наше число итераций может быть записано как (1/2)n^2 - (1/2)n. Для очень большого n термин n^2 намного больше, чем термин n, поэтому мы отбрасываем термин n. Это просто оставляет нас с (1/2)n^2, но другое правило больших O-обозначений - мы не заботимся о постоянном множителе, поэтому мы просто пишем, что это O (n ^ 2).

Answer 5

То, что вы вычислили (n(n-1)/2) - это точное количество итераций для кода. Когда вас спросят о сложности времени с точки зрения большой O, вы даете оценку, которая является достаточно большой, чтобы выразить затраченное время.

Другими словами, вам нужно найти THE SMALLEST power из n, чтобы для некоторых k (k>0), k * n^power было больше, чем точное число итераций. В вашем случае k оказывается 1, а power - 2. Тогда O(n^power) - это сложность вашего времени.

Answer 6

Константы не имеют значения для обозначения big-O.