– O(n) – линейная сложность. Время выполнения пропорционально размеру входных данных.
– O(n log n) – линейно-логарифмическая сложность.
– O(n^2) – квадратичная сложность.
– O(2^n) – экспоненциальная сложность.
Анализ сложности алгоритмов помогает выбрать наилучший алгоритм для решения конкретной задачи, и представляет собой важную часть процесса оптимизации. В этой главе мы также будем рассматривать примеры алгоритмов и их оценку с использованием нотации Big O, чтобы лучше понять, как работает анализ сложности алгоритмов.
Подробно рассмотрим анализ сложности алгоритмов с использованием нотации Big O, чтобы лучше понять, как это работает.
Пример 1: Поиск элемента в списке и почему его сложность составляет O(n) в нотации Big O.
Предположим, у нас есть несортированный список элементов, и нам нужно найти конкретный элемент в этом списке. Простейший способ это сделать – это пройти по всем элементам списка и сравнивать их с искомым элементом, пока не найдем совпадение. В худшем случае, искомый элемент может находиться в самом конце списка, и нам придется пройти через все предыдущие элементы до того, как его обнаружим.
Представьте, что у нас есть список из n элементов, и нам нужно найти элемент x. Мы начинаем с первого элемента и сравниваем его с x. Если элемент не совпадает, мы переходим ко второму элементу и так далее до тех пор, пока не найдем совпадение или не дойдем до конца списка.
Когда мы анализируем время выполнения такого алгоритма, мы видим, что в худшем случае нам приходится пройти через все n элементов списка, чтобы найти искомый элемент. То есть, количество операций, необходимых для завершения алгоритма, пропорционально количеству элементов в списке, т.е., O(n).
Именно поэтому время выполнения алгоритма поиска элемента в несортированном списке оценивается как линейная сложность O(n) в нотации Big O. Это означает, что при увеличении размера списка вдвое, время выполнения алгоритма также увеличится вдвое.
Ни же представлен пример кода, демонстрирующий поиск элемента в несортированном списке и его временную сложность O(n):
```python
def search_unsorted_list(lst, target):
for item in lst:
if item == target:
return True # Элемент найден
return False # Элемент не найден
# Создаем несортированный список
my_list = [4, 2, 9, 7, 1, 5, 8, 3]