Изучение структур данных и алгоритмов неизбежно проведет вас через алгоритмическую сложность и нотацию Big O. Я бы рискнул и сказал, что цель каждого разработчика — писать чистый код и масштабируемые программы. Чтобы достичь этой вехи, нам нужно понять Алгоритмическую Сложность — Большое О, если нужно. Я должен установить рекорд здесь, я люблю вещи, которые масштабируются и, тем более, графическое представление масштабов роста.

Что вообще такое алгоритмическая сложность? Это мера того, сколько времени потребуется для завершения алгоритма при входном размере *n*. Важно помнить, что если программу необходимо масштабировать, она должна вычислять результат в течение конечного и практически ограниченного времени даже для больших значений n.

По этой причине сложность вычисляется асимптотически, когда n приближается к бесконечности. С точки зрения непрофессионала, Big O — это процесс вычисления времени работы алгоритма в математических единицах, чтобы найти ограничения программы или, как правило, производительность «времени выполнения».

Производительность алгоритма в соответствии с правилами анализа большого О измеряется тремя способами: путем определения наилучшего, наихудшего и среднего случая (иногда называемого ожидаемым случаем). Проблема связана со временем, необходимым для выполнения данной задачи. Нотация Big O в основном интересует время выполнения в наихудшем случае, а нотация O в нотации Big O является сокращением от Big Order.

На приведенном выше графике показаны некоторые из распространенных сред выполнения и соотношение между размером ввода n и временем. Чтобы освоить анализ большого О, важно помнить два правила;

  1. Сохраняйте самые быстрорастущие условия
  2. Отбросьте константы.

Помните, что буква «О» в слове «большой О» означает «большой порядок», так что смело опускайте константы, потому что они не так важны.

# -*- 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 является чистый и оптимальный код, более высокая согласованность, что приводит к более быстрым приложениям, лучшей читаемости кода, эффективному рефакторингу, улучшенному рабочему процессу и, что более важно, простой отладке.

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

Удачного взлома!