Это правильное «правило» для идентификации «большого О» обозначения алгоритма?

Я узнал больше о Big O Notation и о том, как рассчитать его на основе написания алгоритма. Я наткнулся на интересный набор «правил» для вычисления нотации алгоритмов Big O и хотел посмотреть, на правильном ли я пути или нет.

Big O Обозначение: N

function(n) {
    For(var a = 0; i <= n; i++) { // It's N because it's just a single loop
        // Do stuff
    }
}

Big O Обозначение: N ²

function(n, b) {
    For(var a = 0; a <= n; a++) {
        For(var c = 0; i <= b; c++) { // It's N squared because it's two nested loops
            // Do stuff
        }
    }
}

Big O Обозначение: 2N

function(n, b) {
    For(var a = 0; a <= n; a++) {
        // Do stuff
    }
    For(var c = 0; i <= b; c++) { // It's 2N the loops are outside each other
        // Do stuff
    }
}

Big O Обозначение: NLogN

function(n) {
    n.sort(); // The NLogN comes from the sort?
    For(var a = 0; i <= n; i++) {
        // Do stuff
    }
}

Верны ли мои примеры и последующие обозначения? Есть ли дополнительные обозначения, о которых я должен знать?

Формально нотация big-O описывает степень сложности.

Чтобы вычислить обозначение big-O:

1. определить формулу сложности алгоритма. Скажем, например, два цикла, в которые вложен еще один цикл, а затем еще три не вложенных цикла:2N² + 3N
2. удалить все, кроме самого высокого срока: 2N²
3. удалить все константы: N²

Другими словами, два цикла, в которые вложен еще один цикл, затем еще три не вложенных цикла - это O (N²)

Это, конечно, предполагает, что в ваших циклах есть простые инструкции. Если у вас есть, например, sort()внутри цикла, вам придется умножить сложность цикла на сложность sort()реализации, используемой вашим языком / библиотекой.

Если вы хотите проанализировать эти алгоритмы, вам нужно определить // dostuff, поскольку это действительно может изменить результат. Предположим, что dostuff требует постоянного O (1) числа операций.

Вот несколько примеров с этим новым обозначением:

Для вашего первого примера, линейный обход: это правильно!

НА):

for (int i = 0; i < myArray.length; i++) {
    myArray[i] += 1;
}

Почему он линейный (O (n))? По мере добавления дополнительных элементов к входу (массиву) количество выполняемых операций увеличивается пропорционально количеству добавляемых элементов.

Поэтому, если для увеличения целого числа где-то в памяти требуется одна операция, мы можем смоделировать работу, которую цикл выполняет, с помощью f (x) = 5x = 5 дополнительных операций. Для 20 дополнительных элементов мы делаем 20 дополнительных операций. Один проход массива имеет тенденцию быть линейным. Так же как и алгоритмы сортировки по сегментам, которые могут использовать структуру данных для сортировки за один проход массива.

Ваш второй пример также будет правильным и выглядит так:

O (N ^ 2):

for (int i = 0; i < myArray.length; i++) {
    for (int j = 0; j < myArray.length; j++) {
        myArray[i][j] += 1;
    }
}

В этом случае для каждого дополнительного элемента в первом массиве i мы должны обработать ВСЕ от j. Добавление 1 к i фактически добавляет (длину j) к j. Таким образом, вы правы! Это шаблон O (n ^ 2), или в нашем примере это фактически O (i * j) (или n ^ 2, если i == j, что часто имеет место с матричными операциями или квадратной структурой данных.

Ваш третий пример, где вещи меняются в зависимости от материала; Если код такой же, как написано, и делать вещи постоянными, то это фактически только O (n), потому что у нас есть 2 прохода массива размера n, а 2n уменьшается до n. Циклы, находящиеся вне друг друга, не являются ключевым фактором, который может генерировать 2 ^ n кода; Вот пример функции 2 ^ n:

var fibonacci = function (n) {
    if (n == 1 || n == 2) {
        return 1;
    }

    else {
        return (fibonacci(n-2) + fibonacci(n-1));
    }
}

Эта функция равна 2 ^ n, потому что каждый вызов функции вызывает два дополнительных вызова функции (Фибоначчи). Каждый раз, когда мы вызываем функцию, объем работы, которую мы должны выполнить, удваивается! Это растет очень быстро, как отрезание головы гидры и появление двух новых прорастаний каждый раз!

Для вашего последнего примера, если вы используете сортировку nlgn, такую ​​как merge-sort, вы правы, что этот код будет O (nlgn). Однако вы можете использовать структуру данных для разработки более быстрых сортировок в определенных ситуациях (например, в пределах известного, ограниченного диапазона значений, например, от 1 до 100). Однако вы правы, считая, что код самого высокого порядка доминирует; таким образом, если сортировка O (nlgn) находится рядом с любой операцией, которая занимает меньше времени O (nlgn), общая сложность времени будет O (nlgn).

В JavaScript (по крайней мере, в Firefox) сортировкой по умолчанию в Array.prototype.sort () действительно является MergeSort, поэтому вы смотрите на O (nlgn) для вашего окончательного сценария.

Ваш второй пример (внешний цикл от 0 до n , внутренний цикл от 0 до b ) будет O ( nb ), а не O ( n ² ). Правило состоит в том, что вы вычисляете что-то n раз, а для каждого из них вы вычисляете что-то еще b раз, поэтому рост этой функции зависит исключительно от роста n * b .

Ваш третий пример - просто O ( n ) - вы можете удалить все константы, поскольку они не растут с n, а рост - это то, что представляет собой нотация Big-O.

Что касается вашего последнего примера, да, ваша нотация Big-O, безусловно, будет исходить из метода sort, который будет, если он основан на сравнении (как это обычно бывает), в наиболее эффективной форме, O ( n * logn ) ,

Напомним, что это приблизительное представление времени выполнения. «Эмпирическое правило» является приблизительным, потому что оно неточное, но дает хорошее приближение первого порядка для целей оценки.

Фактическое время выполнения будет зависеть от того, сколько места в куче, как быстро работает процессор, набор команд, использование префиксных или пост-исправных операторов приращения и т. Д., Yadda. Надлежащий анализ во время выполнения позволит определить принятие, но знание основ позволяет программировать с самого начала.

Я согласен, что вы на правильном пути к пониманию того, как Big-O рационализируется от учебника к практическому применению. Это может быть трудным препятствием для преодоления.

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

Большой ой, по определению означает: для функции f (t) существует функция c * g (t), где c - произвольная постоянная такая, что f (t) <= c * g (t) для t> n, где n является произвольной константой, тогда f (t) существует в O (g (t)). Это математическое обозначение, которое используется в информатике для анализа алгоритмов. Если вы запутались, я бы порекомендовал взглянуть на отношения замыкания, таким образом, вы можете увидеть более детально, как эти алгоритмы получают эти большие-ой значения.

Некоторые следствия этого определения: O (n) фактически совпадает с O (2n).

Также есть много разных типов алгоритмов сортировки. Минимальное значение Big-Oh для сортировки сравнения - O (nlogn), однако существует множество сортов с худшим big-oh. Например, сортировка выбора имеет O (n ^ 2). Некоторые виды, не относящиеся к сравнению, могут иметь лучшие биг-о значения. Например, сортировка ведра имеет O (n).