nlog - мощный инструмент для журналирования и анализа данных

nlog означает, что время работы алгоритма увеличивается логарифмически в зависимости от размера входных данных (n). Это означает, что при увеличении количества входных данных вдвое, время работы алгоритма будет увеличиваться примерно на константу.

Примером алгоритма с временной сложностью nlog может служить алгоритм сортировки слиянием (merge sort). В этом алгоритме исходный массив разбивается на две половины до тех пор, пока каждая половина не будет состоять из одного элемента. Затем элементы сравниваются и объединяются в отсортированный массив. Время выполнения алгоритма сортировки слиянием составляет O(nlogn).

Ниже приведен пример кода на Python, который использует алгоритм сортировки слиянием:

def merge_sort(arr):
    if len(arr) > 1:
        mid = len(arr) // 2
        left_half = arr[:mid]
        right_half = arr[mid:]
        merge_sort(left_half)
        merge_sort(right_half)
        i = j = k = 0
        while i < len(left_half) and j < len(right_half):
            if left_half[i] < right_half[j]:
                arr[k] = left_half[i]
                i += 1
            else:
                arr[k] = right_half[j]
                j += 1
            k += 1
        while i < len(left_half):
            arr[k] = left_half[i]
            i += 1
            k += 1
        while j < len(right_half):
            arr[k] = right_half[j]
            j += 1
            k += 1
    return arr

Этот код разбивает исходный массив на две половины и рекурсивно сортирует каждую половину. Затем он сравнивает элементы из левой и правой половины и объединяет их в отсортированный массив. Время работы алгоритма равно O(nlogn).