Запутать с поведением log (n)

Question

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)) ?

Answer 1

Вы можете фактически посчитать, сколько раз внутренний цикл выполняется в простом случае, подобном этому.Это даст хорошее представление об асимптотическом поведении при изменении 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

Answer 2

Я запутался, является ли это 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, не имеет значения.

Answer 3

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

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

Нет.раз внутренний цикл запускается всегда n.

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