Какая самая распространенная сложность алгоритма
Python
Senior
Без компании
Какая самая распространенная сложность алгоритма
Ответы
Наиболее распространённая сложность алгоритма — **O(n log n)**, так как она встречается во многих эффективных алгоритмах сортировки (например, Merge Sort, QuickSort, HeapSort) и других задачах, связанных с разделением и покорением (divide and conquer).
Пример с Merge Sort:
```
def merge_sort(arr):
if len(arr) > 1:
mid = len(arr) // 2
left = arr[:mid]
right = arr[mid:]
merge_sort(left)
merge_sort(right)
i = j = k = 0
while i < len(left) and j < len(right):
if left[i] < right[j]:
arr[k] = left[i]
i += 1
else:
arr[k] = right[j]
j += 1
k += 1
while i < len(left):
arr[k] = left[i]
i += 1
k += 1
while j < len(right):
arr[k] = right[j]
j += 1
k += 1
```
Также часто встречаются **O(1)**, **O(n)**, **O(n²)** и **O(log n)**, но **O(n log n)** считается золотой серединой между эффективностью и практической применимостью.