Как правильно оценить сложность алгоритма O(n)?

Question

[dc65k]

Разбираюсь с алгоритмами и оценкой их сложности. В нескольких примерах заметил момент в связи, с которым и возник следующий вопрос. Приведу абстрактный пример.
Условно задача решается с помощью цикла:

function f2() {
    const array = Array(100).fill(null);

    return array.reduce((accumulator, currentValue) => {
        return accumulator;
    }, []);
}

Как я понимаю, это линейная сложность алгоритма O(n).

Если задача решается с помощью цикла и в него вложен ещё один цикл:

function f2() {
    const array = Array(100).fill(null);

    for (let i = 0; i < array.length; i++) {
        for (let j = i + 1; j < array.length; j++) {

        }
    }
}

То здесь сложность O(n2)

Вопрос насчёт третьего случая, если задача решается, например, с помощью циклов, которые идут друг за другом:

function f3() {
    const array = Array(100).fill(null);

    return array.reduce((accumulator, currentValue) => {
        return accumulator;
    }, []);
}

В примерах, это тоже это тоже линейная сложность алгоритма O(n).
Но это же не одно и тоже, что и в первом примере выше.

Comments

[Lynn «Кофеман»]

Ни в одном из ваших примеров нет собственно n

Answer 1

[Mercury13]

f(x) = O(g(x)) при x→y — это так называемый символ Ландау.
И означает, что при x, достаточно близких к y, f(x)<k·g(x). Так что 2x или 1000x — извините, не важно.

Отсюда же запись O(log n) — ведь разные логарифмы отличаются на константу, которую символы Ландау съедают.

Чем символы Ландау интересны программистам?
1. Кэшами, быстрым процессором, «хитрым» программированием и прочим на больших наборах данных можно выиграть, например, в разы. Порядком сложности алгоритма — намного, намного больше.
2. Пока закон Мура действовал, объёмы данных росли экспоненциально — так что быстро доходило до того, что программу начинали использовать на наборах данных, для которых она просто не предназначалась.
3. Практически приемлемые алгоритмы обычно имеют небольшую сложность — например, до O(n³). И, например, линейный алгоритм за приемлемое время обработает миллионы элементов, n log n — сотни тысяч, n² — тысячи, n³ — сотни.
4. Программисты отлаживают на небольших наборах данных, которые можно обработать вручную. Так что разница между отладочными и боевыми данными бывает большая — а значит, порядок сложности должен влиять сильнее, чем остальные факторы.

Comments

[Demian Smith]

Отличный ответ.

Answer 2

[Rsa97]

Сложность обозначает, с какой скоростью растёт объём вычислений при увеличении объёма входных данных. В принципе, может получиться что-то наподобие O(2n+5n²+3nlog(n))
Но, так как нас интересует верхняя граница, то мы берём только максимальный член этой суммы, то есть O(5n²). А поскольку хотим получить только относительную скорость роста, то выбрасываем постоянный коэффициент, получая O(n²).
В вашем случае двух последовательных циклов O(2n) сокращается до O(n), что означает, что с ростом объёма входных данных объём вычислений растёт линейно.

Answer 3

[pogoreli]

Да, в первом и последнем случае будет O(n). Но это сокращённый формат, которым все пользуются.

Вообще они не одинаковые. В первом случае это будет O(1*n). В последнем O(3*n).

Но эти константы вообще не важны, потому что big O notation описывает форму функции, а не её конкретные параметры. А обе эти функции- линейные.

Коэффициентами можно принебречь.

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

А биг О скорее о различиях между экспоненциальным, линейными и логорифмическими функциями, а не о конкретных затраченных вычислительных ресурсах.

Answer 4

[Денис Загаевский]

Читай определение О-большого.