Сложность данной функции

Question

Когда я проанализировал сложность сегмента кода ниже, я обнаружил, что это O (n/2). Но при поиске в Интернете я обнаружил, что это, вероятно, O (n). Я хотел бы знать, кто прав.

void function(int n) { 
    int i = 1, k = 100; 
    while (i < n) { 
     k++; 
     i += 2; 
    } 
} 

Answer 1

О (п/2) = O (0,5н) = О (п). См. Wikipedia для получения дополнительной информации об этом.

Если е является O (G), то существуют некоторые с и п, что для всех х> п, | F (х) | < = c * | g (x) |. То есть, с ввода n и далее, c * g (x) доминирует f (x).

Отсюда следует, что О (п/2) = О (п), потому что,

• Если Р (х) = х/2 и г (х) = х, затем устанавливаем c = 0,5 и n = 0.
• Если Р (х) = х и г (х) = х/2, то положим с = 2 и п = 0.

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

Answer 2

Какова точка переменной k в вышеуказанном методе? Независимо от того, что примечание Big-O говорит о поведении в пределе (поскольку значение n приближается к бесконечности). Таким образом, обозначение Big-O не зависит от BOTH коэффициентов масштабирования и констант. Который должен сказать, для любой константы "с" и коэффициент масштабирования "s"

O (f (п)) эквивалентно O (s * f (п) + с)

В вашем случае е (п) = п, с = 1/2, и с = 0. Таким образом, ...

О (п) = О (п/2)

Answer 3

О (п) такая же, как O (n/2)

Идея записи с большими выводами состоит в том, чтобы понять, как быстро алгоритм будет работать, когда вы придаете ему больший ввод. Так, например, если вы удвоите размер вашего ввода, будет ли программа занимать вдвое больше времени или будет занимать в 4 раза больше времени.

Поскольку и n, и n/2 ведут себя одинаково, как вы меняете значение N (например, если вы увеличиваете N в 10 раз, то как N, так и N/2 масштабируются одинаково).