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

Какая сложность сортировки по трём полям?

Ответ: O(n log n), так же как и обычная сортировка одного поля. Количество полей не влияет на асимптотическую сложность.

Почему O(n log n) для любого количества полей?

Время сортировки зависит ТОЛЬКО от количества элементов (n), не от количества полей сравнения:

// Сортировка по одному полю
list.sort((a, b) -> a.getName().compareTo(b.getName()));
// Операций: O(n log n) сравнений

// Сортировка по трём полям
list.sort((a, b) -> {
    int nameComp = a.getName().compareTo(b.getName());
    if (nameComp != 0) return nameComp;
    
    int ageComp = Integer.compare(a.getAge(), b.getAge());
    if (ageComp != 0) return ageComp;
    
    return a.getEmail().compareTo(b.getEmail());
});
// Операций: O(n log n) сравнений
// Каждое сравнение проверяет 3 поля — O(3) = O(1)

Анализ времени

Пусть:
- n = количество элементов
- k = количество полей для сравнения

Время сортировки = O(n log n) * k
                 = O(n log n)  (так как k — константа)

Практический пример

public class Person {
    private String name;
    private int age;
    private String email;
    
    // Comparator для сортировки по 3 полям
    public static final Comparator<Person> COMPARATOR = 
        Comparator.comparing(Person::getName)          // Поле 1
            .thenComparingInt(Person::getAge)         // Поле 2
            .thenComparing(Person::getEmail);         // Поле 3
}

// Использование
List<Person> people = new ArrayList<>();
people.add(new Person("Alice", 30, "alice@example.com"));
people.add(new Person("Bob", 25, "bob@example.com"));
people.add(new Person("Alice", 25, "alice2@example.com"));

// Сортировка по 3 полям: O(n log n)
people.sort(Person.COMPARATOR);

// Результат:
// 1. Alice, 25, alice2@example.com
// 2. Alice, 30, alice@example.com
// 3. Bob, 25, bob@example.com

Анализ компаратора

// Каждое сравнение:
// 1. Сравнивает name O(m) где m — длина строки
// 2. Сравнивает age O(1)
// 3. Сравнивает email O(k) где k — длина email

// Итого на сравнение: O(m + k)
// Количество сравнений: O(n log n)
// Общее время: O((m + k) * n log n)

// Но m и k — константы, поэтому: O(n log n)

Оптимизация: использовать тип данных

// МЕДЛЕННО: String сравнение очень дорого
Comparator<Person> slow = (a, b) -> {
    int nameComp = a.getName().compareTo(b.getName());
    if (nameComp != 0) return nameComp;
    int ageComp = Integer.compare(a.getAge(), b.getAge());
    if (ageComp != 0) return ageComp;
    return a.getEmail().compareTo(b.getEmail());  // O(m)
};

// БЫСТРЕЕ: Comparator.comparing() оптимизирует
Comparator<Person> fast = 
    Comparator.comparing(Person::getName)
        .thenComparingInt(Person::getAge)
        .thenComparing(Person::getEmail);

// ДАЖЕ БЫСТРЕЕ: предварительная сортировка по индексам
list.sort(Comparator.comparingLong(Person::getId));  // Integer index

Теоретическое сравнение

Praktical Performance Test

@Test
public void testSortingComplexity() {
    List<Person> people = generatePeople(1_000_000);
    
    // Сортировка по 1 полю
    long start1 = System.nanoTime();
    people.sort(Comparator.comparing(Person::getName));
    long time1 = System.nanoTime() - start1;
    
    // Сортировка по 3 полям
    long start3 = System.nanoTime();
    people.sort(
        Comparator.comparing(Person::getName)
            .thenComparingInt(Person::getAge)
            .thenComparing(Person::getEmail)
    );
    long time3 = System.nanoTime() - start3;
    
    // Результаты примерно одинаковые или time3 ненамного больше
    // Обе O(n log n), но time3 может быть медленнее из-за длины строк
    System.out.println("Sort 1 field: " + time1 + "ns");     // ~300-500ms
    System.out.println("Sort 3 fields: " + time3 + "ns");    // ~500-700ms
    // Разница из-за сравнения строк, не из-за алгоритма сортировки
}

Когда может быть медленнее?

// МЕДЛЕННО: сравнение тяжелых объектов
Comparator<Person> slow = (a, b) -> {
    // Сравнение больших объектов
    byte[] data1 = a.getAllData();  // O(m) — копирование, сравнение
    byte[] data2 = b.getAllData();
    return Arrays.compare(data1, data2);
};
// Остаётся O(n log n) сравнений, но каждое сравнение дорого

// БЫСТРО: кэшировать данные перед сортировкой
List<CachedPerson> cached = people.stream()
    .map(p -> new CachedPerson(p.getName(), p.getAge(), p.getEmail()))
    .collect(Collectors.toList());

cached.sort(
    Comparator.comparing(CachedPerson::getName)
        .thenComparingInt(CachedPerson::getAge)
        .thenComparing(CachedPerson::getEmail)
);

Рекомендации

// 1. Используй Comparator.comparing() для readability
list.sort(
    Comparator.comparing(Person::getName)
        .thenComparingInt(Person::getAge)
        .thenComparing(Person::getEmail)
);

// 2. Для часто сортируемых данных — кэшируй Comparator
public static final Comparator<Person> SORTER = 
    Comparator.comparing(Person::getName)
        .thenComparingInt(Person::getAge)
        .thenComparing(Person::getEmail);

people.sort(Person.SORTER);

// 3. Если нужна производительность — рассмотри Koltin data classes
// или специализированные сортировки

// 4. Не переживай о количестве полей — O(n log n) в любом случае

Итог

Количество полей для сортировки НЕ влияет на асимптотическую сложность

• Сортировка по 1 полю: O(n log n)
• Сортировка по 3 полям: O(n log n)
• Сортировка по 100 полям: O(n log n)

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