Изучение структур данных и алгоритмов неизбежно проведет вас через алгоритмическую сложность и нотацию Big O. Я бы рискнул и сказал, что цель каждого разработчика — писать чистый код и масштабируемые программы. Чтобы достичь этой вехи, нам нужно понять Алгоритмическую Сложность — Большое О, если нужно. Я должен установить рекорд здесь, я люблю вещи, которые масштабируются и, тем более, графическое представление масштабов роста.
Что вообще такое алгоритмическая сложность? Это мера того, сколько времени потребуется для завершения алгоритма при входном размере *n*
. Важно помнить, что если программу необходимо масштабировать, она должна вычислять результат в течение конечного и практически ограниченного времени даже для больших значений n
.
По этой причине сложность вычисляется асимптотически, когда n
приближается к бесконечности. С точки зрения непрофессионала, Big O — это процесс вычисления времени работы алгоритма в математических единицах, чтобы найти ограничения программы или, как правило, производительность «времени выполнения».
Производительность алгоритма в соответствии с правилами анализа большого О измеряется тремя способами: путем определения наилучшего, наихудшего и среднего случая (иногда называемого ожидаемым случаем). Проблема связана со временем, необходимым для выполнения данной задачи. Нотация Big O в основном интересует время выполнения в наихудшем случае, а нотация O в нотации Big O является сокращением от Big Order.
На приведенном выше графике показаны некоторые из распространенных сред выполнения и соотношение между размером ввода n
и временем. Чтобы освоить анализ большого О, важно помнить два правила;
- Сохраняйте самые быстрорастущие условия
- Отбросьте константы.
Помните, что буква «О» в слове «большой О» означает «большой порядок», так что смело опускайте константы, потому что они не так важны.
# -*- coding: utf-8 -*- """ Created on Tue Apr 12 10:16:23 2022
@author: Andile Jaden Mbele """
def get_squared_nums(nums): squared_nums = [] for n in nums: squared_nums.append(n * n) return squared_nums
nums = [2, 4, 8, 9] get_squared_nums(nums)
# T(n) =>O(n)
Если у нас есть операторы с базовыми операциями, такими как сравнение, присваивание, чтение переменной и т. д., мы предполагаем, что они занимают постоянное время каждый ⇒ T(n) ⇒ O(1)
Приведенный выше код будет Time = a * n + b
, и после применения некоторых правил у нас будет Time = a * n
, и мы продолжаем отбрасывать константы, и у нас остается T(n) = O(n)
# -*- coding: utf-8 -*- """ Created on Tue Apr 12 10:47:21 2022
@author: Andile Jaden Mbele """
def check_duplicates(numbers): for i in range(len(numbers)): for j in range(i+1, len(numbers)): if numbers[i] == numbers[j]: print(numbers[i], " is a duplicate") break
numbers = [3, 6, 2, 4, 3, 6, 8, 9]
#T(n) = a * n^2 + b => O(n^2)
Временная сложность приведенного выше кода равна T(n) ⇒ a * n² + b ⇒ O(n²). На этом этапе, я думаю, мы можем применить некоторые собственные обобщения. Первое обобщение заключается в том, что операторы for loop
приводят к времени выполнения O(n)
, которое является линейным, и если у нас есть два из них, вложенных вместе, наше время выполнения становится O(n * n
), что дает нам O(n^2)
, и это квадратичная сложность. Это медленно, очень ужасно, и этого можно ожидать только от стажеров.
/* Created on Tue Apr 12 10:47:21 2022
@author: Andile Jaden Mbele */ public class Fib { void allFib(int n) { for (int i = 0; i < n; i++) { System.out.println(i + ": " + fib(i)); } }
int fib(int n) { if (n <= 0) { return 0; } else if (n == 1) { return 1; } else { return fib(n - 1) + fib(n - 2); } } }
Кажется неправильным говорить об обозначении большого О и не говорить о рядах Фибоначчи. Приведенный выше код Фибоначчи имеет две ветви на вызов, и мы углубляемся на n
, поэтому время выполнения составляет O(2^n).
.
Вообще говоря, когда вы видите алгоритм с несколькими рекурсивными вызовами, вы смотрите на экспоненциальное время выполнения.
Заключение
Для анализа производительности алгоритма мы используем нотацию Big O. Big O обеспечивает высокоуровневое понимание временной и пространственной сложности алгоритмов. В целом, большим преимуществом Big O является чистый и оптимальный код, более высокая согласованность, что приводит к более быстрым приложениям, лучшей читаемости кода, эффективному рефакторингу, улучшенному рабочему процессу и, что более важно, простой отладке.
Спасибо, что дочитали до этого момента. Надеюсь, вы узнали что-то новое. Я также покажу вам некоторые оптимальные решения для некоторых проблем, описанных здесь в будущем.
Удачного взлома!