Встречается на 1% собеседований по Python

Какая самая распространенная сложность алгоритма

Наиболее распространённая сложность алгоритма — O(n log n), так как она встречается во многих эффективных алгоритмах сортировки (например, Merge Sort, QuickSort, HeapSort) и других задачах, связанных с разделением и покорением (divide and conquer).

Пример с Merge Sort:

python

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) считается золотой серединой между эффективностью и практической применимостью.

Софи собрала все вопросы. Тренируйся и получай
офферы быстрее!

Попробовать бесплатно

Следующий вопрос

Это единственный вопрос по вашему фильтру

Какая самая распространенная сложность алгоритма

Следующий вопрос

Похожие вопросы