Примечание. Эти примеры выполнены на Java, но могут быть применены и к другим языкам.

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

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

Так что же такое «нотация большого О»?

Обозначение Big O - это математическое обозначение, которое описывает ограничивающее поведение функции, когда аргумент стремится к определенному значению или бесконечности. Это член семейства нотаций, изобретенных Полем Бахманном, Эдмундом Ландау и другими, которые в совокупности называются нотацией Бахмана-Ландау или асимптотической нотацией. (см. https://en.wikipedia.org/wiki/Big_O_notation)

Хорошо, я признаю, что объяснений было слишком много. Даже для меня. Простая версия состоит в том, что нотация Big O

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

Фух! .. Со мной так далеко? Если нет, пожалуйста, потратьте еще несколько секунд, чтобы перечитать приведенные выше определения, прежде чем двигаться дальше.

Итак, вы можете спросить себя ... как мне это сделать? Как мне анализировать производительность алгоритма?

Что такое алгоритм?

Прежде всего, давайте начнем с основ, что такое алгоритм?

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

Реальный пример алгоритма начинает работать.

  1. Пешком до вокзала
  2. Попасть в поезд
  3. Выйти из поезда
  4. Идти в офис
  5. Войти в офис

Вот и все! эти 5 простых шагов называются алгоритмом.

Теперь давайте посмотрим на пример кода, что такое алгоритм.

public void printHelloWorld(int amountOfTimesToPrint) {
        for (int x = 0; x < amountOfTimesToPrint; x++) {
            System.out.println("Hello World!");
        }
    }

Довольно просто, правда?

O (1) - Постоянная

Это круто, но как насчет кода? Вот пример очень простого и простого алгоритма в коде:

private int getItemInIndex(int index) {
        return listOfNumbers[index];
    }

Довольно просто, верно!
Итак, у нас есть этот метод или алгоритм, так насколько же быстр этот метод ?? Метод работает в O (1). Это скорость метода.

Так почему же этот метод O (1) быстрый? Поскольку независимо от размера listOfNumbers, требуется всего 1 шаг, чтобы сделать то, что вас просят. Если в listOfNumbers только 1 элемент, это будет O (1), если у него 10 000 элементов, это все равно будет O (1). O (1) называется постоянным временем. Это никогда не меняется.

O (n) - линейный

Это было не так уж плохо. Давайте попробуем еще один, используя предыдущий пример.

private void printEverythingInList(int[] listOfNumbers) {
        for (int number : listOfNumbers) {
            System.out.println(number);
        }
    }

Итак, этот метод выполняется за O (n) времени, которое также называется «линейным временем», где n - количество элементов, в данном случае чисел, в массиве. Таким образом, если в массиве есть 3 элемента внутри, нам придется печатать 3 раза. Если в массиве 51 элемент, нам придется распечатать 51 раз. Имеет смысл, правда?

ПРИМЕЧАНИЕ. n может быть либо размером списка, либо фактическим числом, передаваемым в метод. Имейте это в виду.

public void printHelloWorld(int amountOfTimesToPrint) {
        for (int x = 0; x < amountOfTimesToPrint; x++) {
            System.out.println("Hello World!");
        }
    }
private void printEverythingInList(int[] listOfNumbers) {
        for (int number : listOfNumbers) {
            System.out.println(number);
        }
    }

Оба эти метода выполняются за O (n). Тип ввода метода не имеет значения. Это очень важно

O (n²) - квадратичный

Давайте сделаем еще один шаг.

public void printSomeNumbers(int[] listOfNumbers, int[] listOfMoreNumbers) {
        for (int number : listOfNumbers) {
            for (int numberToo : listOfMoreNumbers) {
                System.out.println("number = " + number + " numberToo = " + numberToo);
            }
        }
    }

Это чрезвычайно простой фрагмент кода. Все, что он делает, - это перебирает 2 разных цикла и распечатывает элементы в каждом цикле. Просто как тот. КАЖДЫЙ раз, когда внешний цикл зацикливается (повторяется), внутренний цикл проходит через ВСЕ свои элементы. Итак, если во внутреннем цикле 10 элементов, а во внешнем - 2 элемента, это будет напечатано 20 раз. По этой причине этот метод работает со скоростью O (n²) или «квадратичное время». Если внешний массив имеет 10 элементов, а внутренний массив 5 элементов, мы должны напечатать 50 раз. Если во внешнем массиве 20 элементов, а во внутреннем массиве также 20 элементов, то нам придется распечатать 400 раз. «O» этого метода - это просто размер двух массивов, умноженных вместе. Не все так сложно, правда?

O (n³) - кубический

public void justLoop(int[] listOfNumbers, int[] listOfMoreNumbers, int[] listOfEvenMoreNumbers) {
        int sizeCombined = listOfNumbers.length() + listOfMoreNumbers.length();
        for (int number : listOfNumbers) {
            for (int numberToo : listOfMoreNumbers) {
                for (i = 0; i < listOfEvenMoreNumbers.size(); i++) {
                    System.out.println("Current most inner index = " + i);
                }
            }
        }
    }

То же, что и в O (n²), каждый внутренний цикл повторяется при повторении каждого внешнего цикла. Каждый раз, когда выполняется итерация первого внешнего цикла, второй внешний цикл начинает перебирать все свои элементы, но для каждой итерации, которую выполняет второй внешний цикл, третий / последний внутренний цикл выполняет итерацию всех своих элементов.

Давайте попробуем несколько математических примеров, которые помогут нам понять, как это можно вычислить, просто используя числа. Допустим, у нас есть следующее уравнение: 25n³ + 10n² + 16

n=1

25(1³) + 10(1²) + 16 = 51

n = 2

25(2³) + 10(2²) + 16 = 256

n = 5

25(5³) + 10(5²) + 16 = 3,391

n = 10

25(10³) + 10(10²) + 16 = 26,016

Что мы здесь видим? Чем больше n, тем менее релевантны 10 (n²) и 16 становится.

Давайте удалим n² и посмотрим, что мы получим, когда n = 10.

25(10³) + 10(10²) = 26,000

Теперь удалим 10 (n²) при n = 10;

25(10³) = 25,000

Разница не так уж велика, и чем больше становится n, тем меньше и меньше значение будет иметь эта часть алгоритма.

Так как этот алгоритм масштабирует, часть, которая действительно имеет прямое отношение к окончательному ответу, который мы получаем, на самом деле является n³. Да, даже не 25. С учетом сказанного мы можем определить, что этот алгоритм - O (n³).

Заключительные слова

Это все. Следите за новостями в следующих сообщениях, где я расскажу о более сложных нотациях Big O, таких как O (log N) и O (n log N) и как анализировать пространственную сложность алгоритма с использованием нотации Big O. Я настоятельно рекомендую перечитать это до тех пор, пока вы не поймете полностью, попробуйте свои собственные примеры или прочитайте больше в Интернете.