Вложенные циклы в записи Big-O?

Question

Возможно, я ошибаюсь в своем понимании нотации Big-O (прошло много времени с тех пор, как я прошел курс по алгоритмам), но мне никогда не приходило в голову следующее:

Это будет считаться O (n ^ 2):

for (int i = 0; i < num_1; i++)
{
    for (int j = 0; j < num_2; j++) 
    {
        cout << i << " " << j << endl;
    }
}

Это будет считаться O (n):

for (int z = 0; z < num_3; z++) { cout << z << endl; }

Моя проблема в том, что касается практических условий. Предположим, что num_1 = 10; num_2 = 20; num_3 = 1000;. В этом случае первый пример, O (n ^ 2), будет выполнять значительно меньше итераций своего внутреннего пространства, чем второй пример O (n).

В более общих терминах: когда num_3 > num_1 * num_2, тогда фрагмент кода O (n ^ 2) делает меньше, чем фрагмент кода O (n). В реальных приложениях эти два фрагмента могут выполнять две совершенно разные задачи, в которых функциональные границы для num_1, num_2 и num_3 значительно различаются. Вложенные num_1 и num_2 могут иметь циклические значения переменных от 0 до 255, но num_3 может часто иметь значения, превышающие миллион.

Почему кодер должен / должен доверять алгоритму или фрагменту на основе их обозначения Big-O, если он не учитывает практические или эксплуатационные границы переменных?

Answer 1

Сказать, что что-то есть в O(n^2) имеет смысл, только если ясно, что должно быть `n´. Обычно это относится к размеру ввода (или, если ввод является числом, это просто относится к этому числу), но в вашем коде неясно, что это за ввод.

for (int i = 0; i < num_1; i++)
{
    for (int j = 0; j < num_2; j++) 
    {
        cout << i << " " << j << endl;
    }
}

Обычно можно сказать, что время выполнения вышеупомянутого фрагмента в O(num_1 * num_2). Если num_1 и num_2 являются константами, это означает, что они находятся в O(1). Если и num_1, и num_2 линейно пропорциональны размеру ввода вашей программы (n), это действительно O(n^2). Если и num_1, и num_2 пропорциональны квадрату размера входного значения, оно равно O(n^4).

Итог: полностью зависит от того, что есть num_1 и num_2, как и как, в зависимости от того, какие факторы они растут.

for (int z = 0; z < num_3; z++) { cout << z << endl; }

Теперь этот код в O(num_3). Чтобы сказать, что это такое с точки зрения n, снова потребуется знать, как num_3 связано с n.

Если все num_1, num_2 и num_3 линейно пропорциональны n, то вы действительно можете сказать, что первый фрагмент выполняется во время O(n^2), а второй в O(n). Однако в этом случае num_3 не может быть больше num_1 * num_2 для достаточно большого n.

Answer 2

Big O описывает скорость алгоритма, а не реальный код.

Когда у вас есть общий алгоритм, вы не знаете, каковы ограничения на переменные.

Answer 3

Big-O дает верхнюю границу или скорость роста в худшем случае. Константы игнорируются, потому что с ростом n они становятся все более и более незначительными (например, вместо O (3 + 2n) вы просто скажете O (n)).

Big-Omega - это показатель роста в лучшем случае, и в зависимости от того, что вы знаете о том, как будет использоваться ваш алгоритм, может быть более подходящим для использования в некоторых ситуациях.

Если Big-O и Big-Omega для данного алгоритма совпадают, то это называется точным порядком, и вы можете исправить это как Big-Theta.

Редактировать: Чтобы уточнить, анализ наихудшего случая часто предпочтительнее, потому что вы хотите иметь возможность сказать клиенту «он всегда будет работать хорошо или лучше», а не «если ваши данные окажутся безупречными, они будут работать великолепно! «

Answer 4

Вы можете думать о Big O для этих примеров в терминах того, как N приближается к бесконечности.

Таким образом, вы правы в своем сценарии, что num_3> num_1 * num_2, но по мере того, как эти три числа становятся большеи больше, это больше не будет иметь место.

Если алгоритм1 равен O (N), а алгоритм2 равен O (N ^ 2), это НЕ означает, что алгоритм1 ВСЕГДА лучше алгоритма2, это просто означает, что естьнекоторое пороговое значение для N (обычно называемое N0), где после этой точки алгоритм1 будет работать лучше, чем алгоритм 2.

Случайный пример - сортировка вставки - O (N ^ 2), где MergeSort - O (N * log (N)), но для очень малых значений N сортировка вставки может на самом деле оказаться быстрее.Как только N становится достаточно большим, MergeSort всегда быстрее.Java-версия функции Arrays.sort на самом деле имеет оператор if, который использует сортировку вставкой для очень малых значений N и модифицированную быструю сортировку или сортировку слиянием для чего-либо большего, чем определенный размер (магическое число около N = 7).

Код Java (в Java 6) для Arrays.sort для массива int выглядит следующим образом:

private static void sort1(int x[], int off, int len) {
    // Insertion sort on smallest arrays
    if (len < 7) {
           //insertion sort
        }

        //modified quick sort
}

В конце дня запись Big Oмеханизм сортировки, который помогает вам быстро анализировать и сравнивать алгоритмы способом, который не зависит от аппаратного обеспечения компьютера и не требует от вас написания, тестирования и времени выполнения ваших различных алгоритмов.Это упрощенное обозначение, поэтому оно никогда не будет точным, и, как показывает только что приведенный пример, оно очень зависит от размера и диапазона ваших данных.

Основным предупреждением для обозначения Big O для алгоритма является то, что вы часто можете вносить улучшения в алгоритм, если вы можете делать предположения о ваших данных.

Answer 5

Обозначение Big O говорит только о том, как долго будет работать алгоритм для данных заданной величины, и как он будет «масштабироваться», когда вы получаете больше данных, алгоритм O (n) может быть медленнее, если он получает больше данных, чем O (n ^ 2) алгоритм (как вы показали на своем примере). Но если вы подаете в 2 раза больше данных в алгоритм O (n), вы должны ожидать в 2 раза больше времени выполнения, а при O (n ^ 2) вы должны ожидать в 4 раза больше.

Answer 6

Нотация big-Oh - это способ выразить вычислительную сложность как функцию скорости роста. Абсолютно необходимо понимать, что это приближение, и оно действительно только для больших значений переменных (например, N).

Вы абсолютно правы в том, что отдельные значения переменных, константы и т. Д. Оказывают большое влияние.

Однако для значений переменных одинакового (и большого) размера выражение big-Oh для набора алгоритмов будет указывать на их относительную производительность. Более типично, однако, это удобный, независимый от реализации способ выразить лучшие, средние и наихудшие сложности алгоритмов.

Однако, в конце дня, как только будет выбран короткий список возможных алгоритмов (вероятно, на основе нотации big-oh и других характеристик, например, требований к пространству и т. Д.), Тогда синхронизация реализации с представительным набором данных путь.