Big-O Обозначение и кодирование

Question

Я изо всех сил пытаюсь обмотать голову, выработав большое количество символов из кода.

Я понимаю основные шаги, т.е.

for (int i = 0; i < n; i++) будет O (п)

И

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

будет O (п)

Я борюсь понять, где и как рассчитать логарифмические значения.

т.е.

Будет:

for (int i = 0; i < n * 2; i++) быть O (журнал N) или O (п § п) или O (журнал 2n) и т.д.

Может кто-то пожалуйста, продемонстрировать в виде кода в качестве примера и как была сформирована нотация.

Я исследовал и продолжаю получать примеры, когда сортировка касается, и списки измельчаются и т. Д., Что имеет смысл в форме, но я, похоже, не получаю, как применять это код, как указано выше.

Я новичок во всем кодировании и большой нотации.

Я знаком с объектами, классами, циклами, функциями, структурами и т. Д. Я занят изучением C++, поскольку это часть моего курса. Мой учебник не объясняет логарифмические вычисления большого числа очень хорошо или почти полностью.

Answer 1

Можно представить код в виде рекуррентного соотношения:

T(n) = T(n-1) + 2 * c, where c = the inner part of the code,

, который мы будем делать 2 * n раз.

Предоставление нам решения, как: T(n) = 2 c n + c_1, where c_1 a constant

А поскольку 2 * c является постоянным, а второе слагаемое, а также постоянная спадает, мы можем написать:

O(n)