Временная сложность — Обозначение Big O

Структуры данных и алгоритмы Примечание

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

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

O(1): доступ к одному элементу в массиве
O(n): линейный поиск
O (log n): двоичный поиск
O (n log n): сортировка слиянием
O(n²): сортировка выбором, сортировка вставками
O(n³)
O (2 ^ n): числа Фибоначчи
O(n!)

В конце также познакомим с правилами вычисления Big O. Начнем!

O(1)

Его также часто называют «постоянным временем», включая такие действия, как прямое получение значения, например: a[0], или использование функции print.

arr1 = [1,2,3,4,5]
pos3 = arr1[2]    # O(1)
print(pos3)    # O(1)

O(n)

Также называемое «линейным временем», означает, что время работы увеличивается линейно с размером n. Например, проверять все элементы массива и каждый раз проверять одно значение.

Линейный поиск

def search(arr, target):
    for i in range(len(arr)):    # O(n)
        if arr[i] == target:
            return i
    return -1
    
    
    
arr = [1,2,3,4,5]
print(search(arr, 3))
>>>>>>>>>>>>>>>>>>>>>>>>
2

Примечание: у вас может возникнуть вопрос: что, если мы запустим search(arr, 1)? Станет ли временная сложность O(1)? Ответ отрицательный, потому что Big O всегда рассматривает наихудший сценарий функции как ее временную сложность.

О (журнал п)

def logn(n):
    count = 0
    while(n > 1):
        n = int(n/2)    # O(log n)
        count += 1
    print(count)
        
        
logn(8)
>>>>>>>>>>>>>>>>>
3

Временная сложность деления n на 2 до определенной ситуации составляет O(log n).

В этом коде нам нужно делить n на 2, пока n=1. Когда n = 8, мы делим 3 раза, чтобы получить 1, что можно рассматривать как log 8 = 3.

Репрезентативным алгоритмом с временной сложностью O(log n) является Двоичный поиск. Поскольку алгоритм делит массив на два подмассива поровну, а затем выбирает подмассивы, соответствующие условиям для следующего шага, продолжайте то же действие до тех пор, пока не будет найдено целевое значение. У меня есть дополнительное объяснение бинарного поиска, не стесняйтесь проверить его в Бинарном поиске — примечание о структурах данных и алгоритмах.

O (n журнал n)

Зная O(n) и O(log n), вам должно быть легко понять, почему временная сложность равна O(n log n) следующего кода:

def nlognfunc(n):
    y = n
    while(n > 1):
        n = int(n/2)    # O(log n)
        for i in range(1, y+1):     #O(n)
            print(i)
            
            
            
nlognfunc(3)
>>>>>>>>>>>>>>>>>>>>>>>>>
1
2
3
1
2
3

Временная сложность: O(n) * O(log n) = O(n log n)

Давайте воспользуемся сортировкой слиянием в качестве практического примера, чтобы объяснить O(n log n):

у нас есть две функции: merge_sort() разбивает массив на небольшой массив и сортирует значения, в то время как merge() в основном выполняет работу по слиянию, сравните значение двух массивы, а меньший поместите в result_array.

ans = merge_sort([1,6,7,3,8,99,403,5])
print(ans)
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
[1, 3, 5, 6, 7, 8, 99, 403]

Каждый раз, когда он вызывает merge_sort(), он будет вызывать merge(), поскольку он рекурсивный, временная сложность составляет O(log n) * O(n ) = O(n log n).

Стоит отметить, что причина, по которой merge()returnresult_arr + left_arr[left_index:] + right_arr[right_index:], заключается в том, что когда цикл while завершается, когда условие не выполняется, один из массивов (левый или правый) добавляется в список результатов, а другой список еще не закончен, может остаться одно или несколько значений, поэтому мы используем [index:], чтобы поместить все левые в result_arr, с другой стороны, [index:] полностью добавленного списка будет пустым списком, который не влияет на результат.

Давайте посмотрим на диаграмму примера merge() ниже:

Примечание. Сортировка слиянием также соответствует концепции алгоритма "разделяй и властвуй".

O(n²)

Обычно произносится как Большое О в квадрате. Вложенный цикл for, который включает один цикл for в цикл for, составляет O(n²). Популярными примерами этого являются сортировка выбором, сортировка вставками. О, худший случай сортировки пузырьком также O(n²)! Если вас интересует разница между этими тремя алгоритмами сортировки, не стесняйтесь переходить по ссылке, чтобы посетить статью: Сравнение сортировки выбором, сортировки вставками и пузырьковой сортировки.

n = 3
count = 0
for i in range(n):    # O(n)
    for j in range(n):    # O(n)
        count += 1
        print(count)
>>>>>>>>>>>>>>>>>>>>>>>>>>
1
2
3
4
5
6
7
8
9

Согласно приведенному выше коду временная сложность составляет O(n) * O(n) = O(n²). В этом случае функция выполняется 9 раз, что равно 3².

O (n³)

Он очень похож на O(n²), но O(n³)обычно представляет собой вложенный цикл for с тремя циклами for.

n = 2
count = 0
for i in range(n):    # O(n)
    for j in range(n):    # O(n)
        for k in range(n):    # O(n)
            count += 1
            print(count)
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
1
2
3
4
5
6
7
8

Временная сложность: O(n) * O(n) * O(n) = O(n³)

O(2^n)

Самый известный пример с временной сложностью O(2^n) — это числа Фибоначчи. Числа Фибоначчи представляют собой последовательность, в которой каждое число является суммой двух предыдущих: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34…

Но как реализовать эту математическую теорию в коде? Это просто, достаточно применить математические формулы для чисел Фибоначчи:

Fn = Fn-1 + Fn-2
F0 = 0 и F1 = 1

тогда это становится кодом, как показано ниже:

def fib(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    return fib(n-1)+fib(n-2)
    
    
print(fib(6))
print(fib(4))
>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
8
3

И почему временная сложность O(2^n)?

Предположим, мы собираемся найти 4-е число в последовательности, то есть F(4). Начнем с F(4), по формуле Fn = Fn-1 + Fn-2 мы знаем, что следующим слоем будет F(3) + F(2) и так далее, пока не остановимся на F(1), F(0).

Из приведенных выше рисунков мы видим, что:

Чтобы найти 4-й номер последовательности, нам нужно ровно 4 слоя, а при расширении до числа n нам нужно всего лишь n слоев.
Каждый раз, когда мы переходим на следующий уровень, становится 2 раза вызова для каждого пункта.

Расположив два приведенных выше абзаца следующим образом, мы можем обнаружить, что итоговая временная сложность приблизительно равна O(2^n):

Каждый следующий уровень, количество шагов удваивается
Всего n слоев
Временная сложность: O(2^n)

O(n!)

Функция, которая выполняется факториально (n!) раз.

def func(n):
    if n == 0:
        print('*****')
        return
    
    for i in range(n):
        func(n-1)
    
func(3)
>>>>>>>>>>>>>>>>>>>>>>
*****
*****
*****
*****
*****
*****

Правила вычисления большого O

Всегда рассматривайте наихудший случай. Представьте себе, когда масштаб данных исчисляется миллиардами.
Удалить константы.

print('1')    # O(1)
for:
 for:         # O( n²)

O(1)+O( n²) = O(1+ n²)=O( n²)

Не обращайте внимания на меньшую.

O( n+n²) = O( n²)

Относитесь к вводу по-разному.

def func(a, b):
    for i in range(a):    # O(a)
    for i in range(b):    # O(b)

Временная сложность должна быть O(a+b) вместо O(2n).

def func(a, b):
    for i in range(a):    # O(a)
        for j in range(b):    # O(b)

Временная сложность должна быть O(a*b) вместо O(n²).

Ссылка

Курс по большой нотации O от freeCodeCamp

Поддержите меня, став участником Medium сегодня и получив доступ к неограниченному количеству статей.

Больше контента на plainenglish.io. Подпишитесь на нашу бесплатную еженедельную рассылку новостей. Получите эксклюзивный доступ к возможностям написания и советам в нашем сообществе Discord.