Смутить поведение log (n)

Alina Khachatrian спросил: 10 мая 2018 в 04:00 в: algorithm
s=0; 
for(i=1;i<n;i=i*2) 
{ 
    for(j=0;j<n;j++)
    {
        s=s+i*j;
    } 
    s=s+1;
}

Я пытаюсь установить большую сложность для вышеуказанного алгоритма. Внешний цикл начинается с 1 и работает до n, счетчик в i удваивается для каждой итерации, таким образом, это log (n ). Внутренний цикл работает от 0 до n с поведением O (n). Я смущен, является ли это O (n log (n)) или нет, порядок имеет значение или нет? Кроме того, j начинается с 0, а не с 1, поэтому это не может быть O (n log (n))?

3 ответа

Есть решение
Shubham ответил: 10 мая 2018 в 04:15

В этом случае внутренний цикл не зависит от внешнего цикла. Таким образом, мы можем просто подсчитать количество попыток внешнего цикла и затем умножить его на количество попыток внутреннего цикла, и это будет сложностью.

Нет. временные пробелы цикла log2(n), поскольку число умножается на 2 каждый раз.

Нет. временных циклов цикла всегда n.

Таким образом, сложность будет O(nlog2(n)).

Mark Meyer ответил: 10 мая 2018 в 04:18

Фактически вы можете подсчитать, сколько раз внутренний цикл работает в таком простом случае. Это даст хороший признак асимптотического поведения при изменении n. Вот пример быстрого javascript:

function count(n) {
    let count=0; 
    for(i=1; i<n; i=i*2) 
    { 
        for(j=0;j<n;j++)
        {
            count++
        } 
       
    }    
    return count
}
let n = 1024
console.log("n:", n, "iterations:", count(n),"nlog(n):", Math.log2(n) * n)

n = 32768
console.log("n:", n, "iterations:", count(n),"nlog(n):", Math.log2(n) * n)

n = 1048576
console.log("n:", n, "iterations:", count(n),"nlog(n):", Math.log2(n) * n)

Поведение выглядит как O (nlog (n)) для меня. Кроме того, разумно, что выполнение циклов log(n), которые выполняются с помощью следующих n, будет O(nlog(n)), потому что n * log(n) === log(n) * n

pjs gchen ответил: 10 мая 2018 в 04:31

Я запутался, является ли это O (n log (n)) или нет

Да, вы правы. Как и вы объяснили, существуют итерации log (n) внешнего цикла и n итерации внутреннего цикла, поэтому O (log (n) n) общая сложность.

порядок имеет значение или нет?

Здесь неважно. например O (log (n) n) == O (n log (n))

Также j начинается с 0, а не с 1, поэтому это не может быть O (n log (n))

Не влияет на сложность. Когда N переходит в бесконечность, начинается с 0 или начинается с 1, не имеет значения.

Дополнительное видео по вопросу: Смутить поведение log (n)

Introduction to Big O Notation and Time Complexity (Data Structures & Algorithms #7)

Big O Part 4 – Logarithmic Complexity