Понимание нотации Big O для исследователей данных
Понимание нотации Big O для исследователей данных
Поскольку наука о данных описывается как пересечение математики, знаний о предметной области и компьютерных наук, большая О-нотация является важнейшим понятием в компьютерных науках. Ее понимание поможет нам разрабатывать более эффективные алгоритмы, оптимизирующие как скорость, так и память, что крайне важно в нашей области, поскольку мы работаем со все большими объемами данных.
В этой статье мы сначала дадим определение нотации big O и расскажем, как она описывает временную и пространственную сложность. Затем мы рассмотрим различные случаи и выведем нотацию big O для каждого из них. Наконец, мы предложим вам несколько упражнений для практической отработки полученных знаний.
Определение нотации big O
Нотация Big O – это математическое выражение, которое описывает эффективность алгоритмов, когда их аргументы стремятся к очень большому числу.
Она используется для описания временной и пространственной сложности данной функции.
Временная сложность – это понятие, описывающее время выполнения функции: сколько времени требуется функции для выполнения своей задачи. Важными факторами для оценки временной сложности могут быть длина массива, количество выполняемых сравнений или количество вызовов рекурсивной функции.
Сложность пространства описывает объем памяти, или пространства, которое должно быть выделено для выполнения вашей функции. Важными факторами для оценки сложности пространства могут быть также длина массива, количество объявленных переменных, количество копий структуры данных и т.д.
Нотация Big O часто используется для описания наихудшего случая из ожидаемых. Мы редко заботимся о лучшем случае.
Например, рассмотрим временную сложность сортировки массива. Наилучшим случаем будет то, что каждый массив, который мы сортируем, уже отсортирован! В этом случае не имеет значения, насколько велик массив. Тогда временная сложность не зависит от размера массива и обозначается как O(1). Однако это не очень полезно знать, поскольку нам редко придется разрабатывать алгоритм сортировки, если все входные массивы уже отсортированы.
Давайте рассмотрим простой пример, чтобы получить представление об обозначении big O.
Получение представления о нотации big O
Рассмотрим следующую ситуацию: вы живете в 5 минутах ходьбы от продуктового магазина и упаковываете каждый товар в отдельную сумку.
Теперь представьте, что у вас есть особенно большой список продуктов, и вы решили купить все, что в нем есть, за один день. Какова временная и пространственная сложность?
Зная, что вы живете в 5 минутах ходьбы от продуктового магазина, доставка пакета с продуктами всегда будет занимать 5 минут, независимо от количества покупаемых вами товаров. Если вы покупаете пакет молока, то вам потребуется 5 минут, чтобы принести его домой. Если вы купите 10 пакетов молока, я
А как насчет пространственной сложности? В этом случае вы упаковываете каждый предмет в отдельную сумку, то есть в одной сумке может находиться только один предмет. Поэтому по мере того, как вы покупаете все больше предметов, количество сумок, которые вам понадобятся, линейно увеличивается: 1 предмет требует 1 сумку, 3 предмета – 3 сумки, 10 предметов – 10 сумок и так далее. Таким образом, пространственная сложность выражается как O(N), где N – количество товаров, которые вы покупаете в продуктовом магазине.
Визуализация пространственной и временной сложности
Теперь, когда у нас есть представление о том, как вывести нотацию big O, давайте посмотрим, как различные выражения сравниваются друг с другом. На рисунке ниже показаны некоторые распространенные обозначения большого О при увеличении N.
Изображение автора. Мы видим, что O(N!) – определенно худший вариант с точки зрения сложности, так как он быстро увеличивается при увеличении N. С другой стороны, O(log(N)) остается относительно ровным по сравнению с другими ситуациями.
Глядя на рисунок выше, можно увидеть, что мы определенно хотим избежать ситуации, когда сложность равна O(N!), поскольку она быстро возрастает при увеличении N.
Вы также можете заметить отсутствие O(1) на графике. Это потому, что трудно разместить линию, избегая ложных выводов. Причина в том, что O(1) не обязательно означает, что это лучше, чем O(N) или O(log(N)). Это просто означает ровную линию, то есть она не увеличивается с ростом N. Однако O(1) может быть медленнее, чем O(N) или O(log(N)).
Таким образом, мы можем уточнить наше определение нотации big O и интерпретировать ее как скорость увеличения сложности времени и пространства.
Разное о нотации Big O
Прежде чем перейти к примерам и упражнениям, приведем различные советы, хитрости и соглашения для нотации big O.
Нам не важны кратные N
Если мы оцениваем сложность функции как O(2N), то это эквивалентно O(N). Аналогично, O(5N) становится O(N). Помните, что большая нотация O описывает, как масштабируется временная и пространственная сложность. Поэтому мы можем смело игнорировать любое кратное N.
Отбросьте недоминирующие члены
Предположим, что у нас есть O(N² + N). Из рисунка выше мы знаем, что O(N²) масштабируется гораздо быстрее, чем O(N). Поэтому O(N² + N) эквивалентно O(N²), так как вклад O(N) при большом N будет минимальным по сравнению с O(N²).
Что такое O(N + log(N))? Снова смотрим на рисунок выше и видим, что O(N) является доминирующим членом, поскольку он увеличивается быстрее, чем O(log(N)). Поэтому O(N + log(N)) эквивалентно O(N).
Когда складывать и умножать?
Мы добавляем сложности, когда операции должны выполняться одна за другой. Рассмотрим приведенный ниже код:
Мы видим, что some_func сначала выполняет итерацию над массивом a, а затем – над массивом b. Таким образом, временная сложность равна O(A + B), где A – длина массива a, а B – длина массива B .
Теперь мы умножаем сложность, когда функция должна выполнять задачу для каждой операции. Это происходит в основном во вложенных циклах for.
Здесь nested_some_func имеет вложенный цикл for, который печатает каждый элемент b для каждого элемента a. Поэтому временная сложность умножается и выражается как O(A * B), где
Предположим, мы хотим вычислить факториал(3), тогда подойдет эта рекурсивная функция:
3 * 2!
3 * 2 * 1!
3 * 2 * 1 = 6
Какова же здесь временная сложность? В данном случае функция выполнилась 3 раза. Таким образом, мы видим линейную зависимость между целым числом и количеством запусков функции. Следовательно, временная сложность равна O(N).
- Теперь мы готовы к выполнению некоторых упражнений.
- Упражнения
- Потратьте время на чтение каждой функции и попытайтесь самостоятельно придумать обозначение временной сложности в виде большого О, прежде чем прокручивать страницу вниз и смотреть объяснение.
Упражнение 1
Ответ Мы дважды итерируем один и тот же массив, что дает нам O(2N), что эквивалентно O(N).
Упражнение 2
Ответ : Это простой оператор if. Поэтому его временная сложность не масштабируется, поэтому это O(1).
Упражнение 3
Ответ : У нас есть вложенный цикл for над одним и тем же массивом. Следовательно, это O(N²). Можно быть более точным и сказать O(A²), где A – длина массива a .
Упражнение 4
Ответ: Рассмотрим пример is_prime(9) . Функция будет делать следующее:
2² меньше 9 и 9 % 2 != 0 . Поэтому мы увеличиваем i до 3.
3² равно 9, так что это последняя проверка. 9 % 3 == 0, поэтому 9 является простым, и функция возвращает True.
А как насчет случая is_prime(11)?
2² меньше 11 и 11 % 2 != 0 . Поэтому мы увеличиваем i до 3.
- 3² меньше 11 и 11 % 3 != 0 . Поэтому увеличиваем i до 4.
- 4² больше 11. Следовательно, 11 является простым, функция возвращает True .
Мы видим, что в худшем случае проверка прекращается, когда i достигает квадратного корня из x. Поэтому временная сложность равна O(sqrt(N)).
- Резюме
- Нотация Big O – это математическое выражение, которое описывает скорость изменения эффективности алгоритма по мере увеличения его аргументов.
- Она используется для выражения как временной, так и пространственной сложности.
Пространственная сложность связана с памятью, которую необходимо выделить для функции. Временная сложность связана со временем, которое требуется для выполнения функции.