Асимптотический анализ — практика

https://www.udemy.com/course/algorithms-and-data-structure/learn/lecture/26307284#overview

Question 1 🟢

// O(n)
function search(arr: number[], x: number): number {
    for (let i = 0; i < arr.length; ++i) {
        if (arr[i] === x) {
            return i + 1;
        }
    }
    return -1;
}

Так как у нас цикл в котором на каждом шагу мы делаем $O(1)$ действий, то выходит $O(n)$

Question 2 🟢

// О(1)
let c = 4;
for (let i = 0; i < c; ++i) {
    console.log(i);
}

Так как делается константное количество действий, то это $O(1)$

Question 3 🟢

// O(n*n)
for (let i = 0; i < n; ++i) {
    for (let j = 0; j < n; ++j) {
        console.log(i + ' ' + j);
    }
}

Так как у нас 2 цикла друг в друге и каждый идет до n, то выходит $O(n\ast n)$

Question 4 🟢

// O(log(n))
let sum = 0;
while (n !== 0) {
    sum += n % 10;
    n = Math.floor(n / 10);
}

Так как у нас цикл в котором на каждом шагу мы уменьшаем наше n в 10 раз, значит, что цикл будет работать $log10(n)$ раз, и так как в цикле действия оцениваются в $O(1)$, то выходит $O(log(n))$

Question 5 🟢

// O(n + m)
for (let i = 0; i < n; ++i) {
    console.log(i);
}
for (let i = 0; i < m; ++i) {
    console.log(i);
}

Так как у нас 2 цикла друг за другом, один идет до n, а другой до m, и у нас нет никакой связи между n и m, то мы вынуждены писать $O(n+m)$, потому что однозначно не известно кто из них больше.

Question 6 🔴

// O(n ^ 5)
for (let i = 0; i < n; ++i) {
    for (let j = 0; j < n * n; ++j) {
        for (let k = 0; k < j; ++k) {
            console.log(i + ' ' + j + ' ' + k);
        }
    }
}

Самый внутренний делает приблизительно $n^2/2$ действий, что значит это $O(n^2)$. Добавляя внешние циклы получаем $O(n^5)$

Question 7 🟢

// O(n * sqrt(n))
for (let i = 0; i < n; ++i) {
    for (let j = 0; j * j <= n; ++j) {
        console.log(i + j);
    }
}

Переписав условие второго цикла как j < sqrt(n), мы получим $O(n\ast sqrt(n))$