Нотация Big o в структуре данных: все, что нужно знать

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

Обозначение Big O относится к математическому обозначению, которое действует как ограничивающий фактор любой функции, когда аргумент более склонен к определенному значению или бесконечности. Он относится к категории математических обозначений, изобретенных Эдмундом Ландау, Паулем Бахманом и другими. Следовательно, это вместе называется обозначением Бахмана – Ландау или асимптотическим обозначением.

В соответствии с математическим выводом две функции, f (n) и g (n) , определены на наборе положительных или действительных чисел, которые не связаны. Здесь g(n) строго положителен для любого большого значения n. Его можно записать в следующем виде:

f(n) = O(g(n)) , в котором n стремится к бесконечности (n → ∞)

Однако здесь предположение о бесконечности n не определено исключительно, и поэтому приведенное выше выражение можно записать как:

е (п) = О (г (п))

Здесь f и g — необходимые функции, которые начинают с положительных целых чисел до вещественных чисел, которые не являются неотрицательными.

Следовательно, большие значения n обозначаются асимптотикой Big O.

Свойства нотации Big O в структуре данных

Алгоритм Big O в структуре данных имеет немало обязательных свойств. Упомянутые существенные свойства нотации Big O заключаются в следующем:

• Функция суммирования:
  Если f(n) = f 1 (n) + f 2 (n) + - + f m (n) и f i (n)≤ f i +1(n) ∀ i=1, 2,–, m,
  тогда O(f(n)) = O(max(f1(n), f2(n), –, fm(n))).
• Логарифмическая функция:
  Если f(n) = logan и g(n)=logbn,
  тогда O (f (n)) = O (g (n))
• Постоянное умножение:
  Если f(n) = cg(n), то O(f(n)) = O(g(n)), где c — ненулевая константа.
• Полиномиальная функция:
  Если f(n) = a0 + a1.n + a2.n2 + — + am.nm,
  тогда O(f(n)) = O(nm).

Изучайте онлайн-курсы по разработке программного обеспечения в лучших университетах мира. Участвуйте в программах Executive PG, Advanced Certificate Programs или Master Programs, чтобы ускорить свою карьеру.

Изучите наши популярные курсы по программной инженерии

Здесь, обращаясь к Big O, каждая отдельная функция журнала увеличивается одинаково.

Важность нотации Big O при анализе алгоритмов во время выполнения

Сложность времени работы алгоритма в наихудшем случае используется для проведения сравнений и расчетов, особенно в случае анализа производительности алгоритма. Порядок O (1), обозначенный как постоянное время выполнения, является самым быстрым временем выполнения алгоритма — время, которое требуется алгоритму, одинаково для различных размеров входных данных. Важно отметить, что идеальное время выполнения алгоритма — это постоянное время выполнения, которое достигается очень редко, поскольку время выполнения алгоритма зависит от входного размера n.

Например:

Как упоминалось выше, производительность алгоритма во время выполнения в значительной степени зависит от входного размера n. Поясним этот факт несколькими математическими примерами, чтобы выполнить анализ времени выполнения алгоритма для различных размеров n:

• п = 20
  log (20) = 2,996;
  20 = 20;
  20 log (20) = 59,9;
  20 2 = 400;
  2 20 = 1084576;
  20! = 2,432902 + 18 18 ;
• п = 10
  лог (10) = 1;
  10 = 10;
  10 log (10) = 10;
  10 2 = 100;
  2 · 10 = 1024;
  10! = 3628800;

Точно так же рассчитывается производительность алгоритма во время выполнения.

Вот несколько других алгоритмических примеров анализа времени выполнения:

• Когда дело доходит до линейного поиска, сложность выполнения составляет O(n).
• Сложность выполнения составляет O(log n) для бинарного поиска.
• Для сортировки выбором, пузырьковой сортировкой, сортировкой сегментов, сортировкой вставками сложность выполнения составляет O (n ^ c).
• Когда дело доходит до экспоненциальных алгоритмов, таких как Ханойская башня, сложность выполнения составляет O(c^n).
• Для сортировки слиянием и сортировки кучей сложность времени выполнения составляет O (n log n).

Как Big O анализирует сложность пространства?

Определение пространственной и временной сложности алгоритма является важным шагом. Это связано с тем, что мы можем определить время выполнения, которое требуется алгоритму, анализируя производительность алгоритма во время выполнения и объем памяти, занимаемый алгоритмом, путем анализа пространственной сложности алгоритма. Следовательно, чтобы измерить пространственную сложность алгоритма, мы должны сравнить производительность алгоритма по пространственной сложности в наихудшем случае.

Для определения пространственной сложности алгоритма мы должны выполнить следующие две задачи:

Задача 1: Очень важно реализовать программу для конкретного алгоритма.

Задача 2: важно знать размер входных данных n, чтобы определить объем памяти, который будет хранить каждый элемент.

Эти две важные задачи должны быть выполнены перед вычислением пространственной сложности алгоритма.

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

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

• Для пузырьковой сортировки, линейного поиска, сортировки выбором, сортировки вставками, сортировки кучей и двоичного поиска пространственная сложность равна O(1) .
• Когда дело доходит до сортировки по основанию , сложность пространства составляет O(n+k) .
• Сложность пространства составляет O (n) для быстрой сортировки.
• Сложность пространства составляет O (log n) для сортировки слиянием.

Пример нотации Big O в C

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

Ниже вы найдете алгоритм сортировки выбором в C, где была рассчитана сложность алгоритма в наихудшем случае (обозначение Big O):

for(int я=0; я<n; я++)

{

интервал мин = я;

for(int j=i; j<n; j++)

{

если(массив[j]<массив[мин])

мин=j;

}

интервал времени = массив [i];

массив[i] = массив[мин];

массив [мин] = темп;

}

Для анализа алгоритма:

• Уже можно обозначить, что диапазон внешнего цикла for равен i < n , что означает, что порядок цикла равен O(n).
• Затем мы можем определить, что это также O (n), поскольку j < n для внутреннего цикла for.
• Константа игнорируется, даже если найдена средняя эффективность n/2 для константы c. Итак, порядок O(n).
• После умножения порядка внутреннего цикла и внешнего цикла достигается сложность выполнения O (n ^ 2).

Другие алгоритмы на C могут быть легко реализованы, где сложности могут быть легко проанализированы и определены аналогичным образом.

Использование нотации большого O

Есть две основные области, в которых применяется нотация Big O:

• Математика : нотация большого O довольно часто используется в области математики для описания того, как конечный ряд близко аппроксимирует функцию, особенно когда речь идет о случаях асимптотического расширения или усеченного ряда Тейлора.
• Информатика: общеизвестно, что нотация Big O в основном используется в области информатики из-за ее полезности при анализе алгоритмов.

Однако в обоих приложениях функция g ( x ), появляющаяся внутри O (·), часто выбирается как наиболее простая, если опущены члены более низкого порядка и постоянные множители.

Есть два других использования этого обозначения, которые формально близки, но относительно различны. Они есть:-

• Бесконечная асимптотика
• Инфинитезимальная асимптотика.

Однако это различие не в принципе, а только в применении, поскольку формальное определение «Большого О» одинаково для обоих случаев. Единственная разница заключается в ограничениях на аргумент функции.

Прочтите наши популярные статьи, связанные с разработкой программного обеспечения

Вывод

В заключение мы можем сказать, что большие данные играют неотъемлемую роль в структурах данных, и наличие глубоких и всесторонних знаний о нотации Big O является отличным навыком, которым необходимо обладать. Он пользуется большим спросом в сфере труда и потенциально может стать отличным выбором для карьерного роста. Расширенная программа сертификатов upGrad в области больших данных даст вам рычаги, необходимые для продвижения по карьерной лестнице. Он познакомит вас с высшими профессиональными навыками, такими как обработка данных с помощью PySpark, хранилище данных, MapReduce, обработка больших данных в облаке AWS, обработка в реальном времени и т. д.