Базово про O(n*log(n))

• Вспомнишь, что такое логарифм.
• Узнаешь, в каких случаях возникает сложность O(n*log(n)).
• Научишься оценивать сортировки по времени и памяти.

Логарифм log_b(N) отвечает на вопрос: «Сколько раз нужно разделить N на b, чтобы в результате получить 1?». b - это основание логарифма.

Для log_2(N): если N = 8 , то деления 8 → 4 → 2 → 1 занимают 3 шага (log_2(8)=3).

Обычно в записи O(log(n)) не указывают основание логарифма, потому что при асимптотической оценке важна только сама форма зависимости, а основание — константа.

n*log(n) называют линейно-логарифмической сложностью. По скорости работы она расположена между O(n) (линейной) и O(n*n) (квадратичной). Чтобы понять, как сильно n*log(n) отличается от n, взгляни на таблицу:

Хотя n*log(n) растёт быстрее, чем n, на практике такая сложность всё равно считается достаточно быстрой и ближе к O(n), чем к O(n*n).

Чаще всего такая оценка возникает в алгоритмах сортировки:

using System;
using System.Collections.Generic;

public class Solution {
    static Solution() {
        List<int> nums = new List<int> {1, 5, 2, 3, 5, 1, 2, 3};
        // Сортировка за O(n*log(n))
        nums.Sort();
        // [1, 1, 2, 2, 3, 3, 5, 5]
        Console.WriteLine(string.Join(" ", nums));
    }
}

#include <vector>
#include <algorithm>
#include <iostream>

using namespace std;

// Сортировка за O(n*log(n))
__attribute__((constructor)) void run() {
    vector<int> nums = {1, 5, 2, 3, 5, 1, 2, 3};
    sort(nums.begin(), nums.end());
    // [1, 1, 2, 2, 3, 3, 5, 5]
    for (int num : nums) {
        cout << num << " ";
    }
    cout << endl;
}

package main

import (
    "fmt"
    "sort"
)

func init() {
    nums := []int{1, 5, 2, 3, 5, 1, 2, 3}
    // Сортировка за O(n*log(n))
    sort.Ints(nums)
    // [1, 1, 2, 2, 3, 3, 5, 5]
    fmt.Println(nums)
}

import java.util.*;

public class Solution {
    static {
        List<Integer> nums = new ArrayList<>(Arrays.asList(1, 5, 2, 3, 5, 1, 2, 3));
        // Сортировка за O(n*log(n))
        Collections.sort(nums);
        // [1, 1, 2, 2, 3, 3, 5, 5]
        System.out.println(nums);
    }
}

nums = [1,5,2,3,5,1,2,3]
# Сортировка за O(n*log(n))
nums.sort()
# [1, 1, 2, 2, 3, 3, 5, 5]
print(nums)

// Сортировка за O(n*log(n))
export function run() {
    const nums = [1, 5, 2, 3, 5, 1, 2, 3];
    nums.sort((a, b) => a - b);
    // [1, 1, 2, 2, 3, 3, 5, 5]
    console.log(nums);
}

Также сложность O(n*log(n)) встречается и в других алгоритмах, но в этом курсе мы их рассматривать не будем, так как они редко встречаются на практике.

Сортировка — это упорядочивание набора данных (чисел, слов или других объектов) по определённому правилу (например, по возрастанию или убыванию).

Пример: если мы отсортируем массив [4,2,5,6,1] по возрастанию, получим [1,2,4,5,6].

Существует множество алгоритмов сортировки, и каждый из них лучше работает для тех или иных данных. Чаще всего сортировки имеют оценку по времени O(n*log(n)), а по памяти — O(1), O(log(n)) или O(n).

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

Такие оценки по времени и памяти связаны с внутренним устройством каждого алгоритма. Мы не будем подробно разбирать их в этом курсе. Важно лишь помнить, что большинство эффективных сортировок имеют время работы порядка O(n*log(n)).

Дополнительное задание: узнай, какая сортировка используется в языке программирования, которым ты пользуешься, и выясни, какова её оценка по времени и памяти.

1. Чаще всего сортировка оценивается по времени как O(n*log(n)), а по памяти — O(n), O(log(n)) или O(1) в зависимости от конкретного алгоритма.
2. Оценка O(n*log(n)) чаще всего возникает при использовании сортировок.
3. Логарифм log_b(N) отвечает на вопрос: “Сколько раз нужно разделить N на b, чтобы получить 1?”