Это всего лишь проверка цикла for 1/3n раз, так что, я думаю, он все еще технически линейный? Однако я действительно не понимаю, почему это не будет O (logn), потому что много раз код с временем выполнения O (logn) заканчивается проверкой около 1/3 n. Всегда ли O(logn) каждый раз делит варианты на 2?
int a = 0;
for (int i = 0; i < n; i = i+3)
a = a+i;
ваш код имеет сложность O(n), O(n)/3 == a * O(n) == O(n)
При анализе временной сложности постоянные факторы не имеют значения. Вы можете выполнить 1 000 000 операций за цикл, и это все равно будет O (n). Поскольку константа 1/3 не имеет значения, это все равно O(n). Если у вас есть n на уровне 1 000 000, то 1/3 от n будет намного больше, чем log n.
Из статьи Википедии о нотации Big-O:
Пусть k — константа. Затем:
O(kg) = O(g) if k is nonzero.
n = n-2;, следующий за a = a+i;? Что было бы в этом случае Big-O?
- person user3251142; 19.03.2014
n/5 вместо n/3 (используя исходное значение n). Я предполагаю, что вы добавите фигурные скобки, чтобы n=n-2 было частью цикла.
- person ajb; 19.03.2014
for по-прежнему пропорционально исходному значению n.
- person rgettman; 19.03.2014
2*c и /3 — это операции с константами. Это все еще O (n). Способ сделать такой цикл O(log n) состоит в том, чтобы либо делить n на константу в каждом цикле, либо умножать i на константу в каждом цикле.
- person rgettman; 19.03.2014
if (n%3 == 2) n = 9;. Если бы n имел остаток 2, код закончился бы очень быстро! Не создает ли это огромную дисперсию?
- person user3251142; 19.03.2014
if, но это все еще постоянный множитель, поэтому среднее значение по-прежнему равно O (n). Боюсь, вычисление дисперсии или стандартного отклонения выше моих сил.
- person ajb; 19.03.2014
Это порядок O(n), а не O(logn). Это потому, что время работы увеличивается линейно с увеличением n
Для получения дополнительной информации взгляните на этот график, и, надеюсь, вы поймете, почему он не регистрируется https://www.cs.auckland.ac.nz/software/AlgAnim/fig/log_graph.gif
Время работы O(n) (в единицах измерения сложности).
;послеi = i + 3является синтаксической ошибкой. - person ajb schedule 19.03.2014