Как показать зависимость скорости от O(nlogn)?

Для демонстрации зависимости скорости выполнения программы от O(n log n) можно написать код на Python, к примеру, сортировку элементов массива. Алгоритм сортировки, имеющий сложность O(n log n), это быстрая сортировка (quick sort) или сортировка слиянием (merge sort).

Вот пример кода, который демонстрирует зависимость скорости сортировки от O(n log n):

import random
import time

# Функция для генерации случайного массива
def generate_array(size):
    return [random.randint(1, 1000) for _ in range(size)]

# Функция для сортировки массива с использованием quick sort
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        less = [x for x in arr[1:] if x <= pivot]
        greater = [x for x in arr[1:] if x > pivot]
        return quick_sort(less) + [pivot] + quick_sort(greater)

# Генерируем массивы разных размеров и сортируем их
for i in range(1, 6): # i от 1 до 5
    array_size = 10**i
    arr = generate_array(array_size)

    start_time = time.time()
    sorted_arr = quick_sort(arr)
    end_time = time.time()

    print(f"Размер массива: {array_size}, Время выполнения: {end_time - start_time} секунд")

В этом коде мы генерируем массивы разного размера, затем сортируем их с помощью quick sort и замеряем время выполнения. При увеличении размера массива в 10 раз (от 10 до 100000 элементов), время выполнения увеличивается близко к логарифмической зависимости O(n log n). Таким образом, мы можем наблюдать зависимость скорости выполнения от O(n log n) на практике.