Когда и как мы должны добавить к сложности времени при вычислении Big O нотации функции - PullRequest
Новая
       25

Когда и как мы должны добавить к сложности времени при вычислении Big O нотации функции

0 голосов
/ 02 апреля 2020

Я пытаюсь узнать, как вычислить Big O Нотацию функции. Я не очень понимаю, когда мы должны добавить эти "N" числа, а когда нет

, я напишу пример с использованием псевдокода, чтобы вы поняли мою идею 

define function x(n){
    for( i = 1 ; i < n; i++){
        for ( j = 1 ; j < n; j++){
             // Statement
        }
    }
}

Здесь, первый для l oop занимает n времени для выполнения, я понял, что секунда для l oop также занимает n времени для выполнения. Так как это вложенное значение для l oop, то есть одно для l oop внутри другого, мы умножаем значения, поэтому получаем n ^ 2 , это означает, что нотация Big O будет выглядеть как это ==> O (n ^ 2)

Теперь, если бы у нас было al oop рядом друг с другом, мы добавили бы n ценности. например: 

define function x(n){
    for ( i = 1 ; i < n ; i++){
        // Statement
    }
    for ( j = 1 ; j < n ; j++){
        // Statement
    }
}

Теперь первая функция занимает n времени для выполнения, а вторая функция также занимает n времени для выполнения. Итак, мы добавляем значения и получаем 2n , поэтому запись Big O будет выглядеть следующим образом ==> O (n)

Теперь вот моя проблема: 

define function x(n){
    p = 0 
    for( i = 1; i < n ; i *= 2){
        p++;
    }
    for( j = 1 ; j < p ; j *= 2){
        // Statement
    }
}

Итак, здесь первая функция берет log2 (n), что для меня понятно, я понял почему. После этой функции переменная p будет log2 (n). Итак, секунде для l oop потребуется время log2 (p), то есть log2 (log2 (n)).

Теперь я смотрел видео на YouTube, в котором говорилось, что мы не добавляем значения и что для обозначения Big O функции остается время, необходимое для секунды для l oop, которое равно log2 (p), поэтому O (log2 (log2 (p))) * . Так что это моя проблема, почему бы нам не сложить время, необходимое для первого l oop, со временем, необходимым для второго l oop, как мы это делали раньше. Таким образом, у нас было бы что-то вроде log2 (n) + log2 (log2 (n))? Почему мы должны сказать, что Big O Нотация этой функции - это время, необходимое для второго l oop, мы игнорируем первое l oop в конце?

1 Ответ

1 голос
/ 02 апреля 2020

Это правда, что первый l oop принимает O (log (n)), и, следовательно, p примерно log (n).

Таким образом, вторая l oop имеет сложность log2 (log2 (n)), которая асимптотически растет медленнее, чем первая l oop.

Если вас спросят о сложности из всего кода преобладает первый l oop, поэтому это log2 (n).

Видео, на которое вы ссылаетесь, запрашивает только о втором l oop, который является log2 (log2 (n)).

...