Основы алгоритмов: анализ сложности, Big-O-нотация, поиск и сортировка

Этот материал представляет собой подробное введение в основы алгоритмов, включая анализ сложности, Big-O-нотацию, алгоритмы поиска и сортировки с практическими примерами.

In a Nutshell

Алгоритмы — это пошаговые инструкции для решения задач. Big-O-нотация описывает их сложность, алгоритмы поиска находят элементы, алгоритмы сортировки упорядочивают данные.

Основные определения

Алгоритмы представляют собой чётко определённую конечную последовательность операций для решения задачи. Они являются фундаментом информатики и разработки программного обеспечения.

Анализ сложности:

• Временная сложность: количество операций как функция размера входных данных
• Пространственная сложность: требуемый объём памяти
• Big-O-нотация: верхняя граница сложности
• Best/Average/Worst Case: различные сценарии времени выполнения

Big-O-нотация (основные виды):

• O(1): постоянное время
• O(log n): логарифмическое время
• O(n): линейное время
• O(n log n): линейно-логарифмическое время
• O(n²): квадратичное время
• O(2ⁿ): экспоненциальное время

Ключевые моменты

• Алгоритмы: чётко определённая последовательность операций для решения задачи
• Big-O-нотация: математическое описание сложности
• Временная сложность: количество операций в зависимости от размера входных данных
• Алгоритмы поиска: Linear Search (O(n)), Binary Search (O(log n))
• Алгоритмы сортировки: Bubble Sort (O(n²)), Quick Sort (O(n log n))
• Best/Worst/Average Case: различные сценарии времени выполнения
• Практическое применение: основа для эффективной разработки

Основные компоненты

1. Концепция алгоритма: входные данные, обработка, вывод
2. Анализ сложности: требования по времени и памяти
3. Big-O-нотация: асимптотический анализ
4. Алгоритмы поиска: линейный и бинарный поиск
5. Алгоритмы сортировки: различные стратегии сортировки
6. Структуры данных: массивы, списки, деревья, графы
7. Рекурсия: самовызывающиеся алгоритмы
8. Divide and Conquer: решение задач путём разбиения

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

1. Big-O-нотация и анализ сложности

import java.util.*;

public class Komplexitaetsanalyse {
    
    // O(1) - Konstante Zeit
    public int getFirstElement(int[] array) {
        if (array.length == 0) {
            throw new IllegalArgumentException("Array ist leer");
        }
        return array[0];  // Immer eine Operation
    }
    
    // O(n) - Lineare Zeit
    public int findMax(int[] array) {
        if (array.length == 0) {
            throw new IllegalArgumentException("Array ist leer");
        }
        
        int max = array[0];
        for (int i = 1; i < array.length; i++) {  // n Operationen
            if (array[i] > max) {
                max = array[i];
            }
        }
        return max;
    }
    
    // O(n²) - Quadratische Zeit
    public void printPairs(int[] array) {
        for (int i = 0; i < array.length; i++) {        // n Schleifen
            for (int j = 0; j < array.length; j++) {    // n Schleifen
                System.out.println(array[i] + ", " + array[j]);
            }
        }
        // Gesamt: n * n = n² Operationen
    }
    
    // O(log n) - Logarithmische Zeit
    public int powerOfTwo(int n) {
        int result = 1;
        while (n > 0) {  // log₂(n) Schleifendurchläufe
            result *= 2;
            n /= 2;
        }
        return result;
    }
    
    // O(n log n) - Linearithmische Zeit
    public void mergeSort(int[] array) {
        if (array.length <= 1) {
            return;
        }
        
        int mid = array.length / 2;
        int[] left = Arrays.copyOfRange(array, 0, mid);
        int[] right = Arrays.copyOfRange(array, mid, array.length);
        
        mergeSort(left);    // O(log n) Rekursionstiefe
        mergeSort(right);
        
        merge(array, left, right);  // O(n) für jeden Merge
    }
    
    private void merge(int[] result, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;
        
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                result[k++] = left[i++];
            } else {
                result[k++] = right[j++];
            }
        }
        
        while (i < left.length) {
            result[k++] = left[i++];
        }
        
        while (j < right.length) {
            result[k++] = right[j++];
        }
    }
    
    // O(2ⁿ) - Exponentielle Zeit
    public int fibonacci(int n) {
        if (n <= 1) {
            return n;
        }
        return fibonacci(n - 1) + fibonacci(n - 2);  // 2ⁿ Aufrufe
    }
    
    // Komplexitätsanalyse mit Zeitmessung
    public void analyzeComplexity() {
        int[] sizes = {100, 1000, 10000, 100000};
        
        System.out.println("=== Komplexitätsanalyse ===");
        System.out.println("Größe\tO(1)\tO(n)\tO(n²)\tO(log n)");
        
        for (int size : sizes) {
            int[] array = new int[size];
            
            // Array mit Zufallszahlen füllen
            Random random = new Random();
            for (int i = 0; i < size; i++) {
                array[i] = random.nextInt(1000);
            }
            
            // O(1) messen
            long start = System.nanoTime();
            getFirstElement(array);
            long o1Time = System.nanoTime() - start;
            
            // O(n) messen
            start = System.nanoTime();
            findMax(array);
            long onTime = System.nanoTime() - start;
            
            // O(n²) messen (nur für kleine Arrays)
            long on2Time = 0;
            if (size <= 1000) {
                start = System.nanoTime();
                printPairs(array);
                on2Time = System.nanoTime() - start;
            }
            
            // O(log n) messen
            start = System.nanoTime();
            powerOfTwo(size);
            double olognTime = System.nanoTime() - start;
            
            System.out.printf("%d\t%d\t%d\t%d\t%.0f%n",
                             size, o1Time, onTime, on2Time, olognTime);
        }
    }
    
    public static void main(String[] args) {
        Komplexitaetsanalyse analyse = new Komplexitaetsanalyse();
        
        // Komplexitätsanalyse
        analyse.analyzeComplexity();
        
        // Big-O Demonstration
        System.out.println("\n=== Big-O Demonstration ===");
        demonstrateBigO();
        
        // Rekursion vs Iteration
        System.out.println("\n=== Rekursion vs Iteration ===");
        compareRecursionIteration();
    }
    
    private static void demonstrateBigO() {
        int n = 1000;
        Komplexitaetsanalyse demo = new Komplexitaetsanalyse();
        
        System.out.println("Demonstration mit n = " + n);
        
        // O(1) Beispiel
        int[] array = {1, 2, 3, 4, 5};
        System.out.println("O(1) - Erstes Element: " + demo.getFirstElement(array));
        
        // O(n) Beispiel
        int[] largeArray = new int[n];
        for (int i = 0; i < n; i++) {
            largeArray[i] = i;
        }
        System.out.println("O(n) - Maximum: " + demo.findMax(largeArray));
        
        // O(log n) Beispiel
        System.out.println("O(log n) - 2^" + n + " = " + demo.powerOfTwo(n));
        
        // O(n log n) Beispiel
        int[] sortArray = new int[100];
        Random random = new Random();
        for (int i = 0; i < 100; i++) {
            sortArray[i] = random.nextInt(1000);
        }
        System.out.println("O(n log n) - Merge Sort durchgeführt");
        demo.mergeSort(sortArray);
        
        // O(n²) Beispiel (kleines Array)
        int[] smallArray = {1, 2, 3, 4, 5};
        System.out.println("O(n²) - Alle Paare:");
        demo.printPairs(smallArray);
    }
    
    private static void compareRecursionIteration() {
        Komplexitaetsanalyse demo = new Komplexitaetsanalyse();
        int n = 30;
        
        System.out.println("Fibonacci n = " + n);
        
        // Rekursive Version (exponentiell)
        long start = System.nanoTime();
        int recursiveResult = demo.fibonacci(n);
        long recursiveTime = System.nanoTime() - start;
        
        // Iterative Version (linear)
        start = System.nanoTime();
        int iterativeResult = fibonacciIterative(n);
        long iterativeTime = System.nanoTime() - start;
        
        System.out.println("Rekursiv: " + recursiveResult + " (" + recursiveTime + "ns)");
        System.out.println("Iterativ: " + iterativeResult + " (" + iterativeTime + "ns)");
        System.out.println("Speedup: " + (recursiveTime / iterativeTime) + "x");
    }
    
    private static int fibonacciIterative(int n) {
        if (n <= 1) return n;
        
        int a = 0, b = 1;
        for (int i = 2; i <= n; i++) {
            int temp = a + b;
            a = b;
            b = temp;
        }
        return b;
    }
}

2. Алгоритмы поиска

import java.util.*;

public class Suchalgorithmen {
    
    // Lineare Suche - O(n)
    public static int linearSearch(int[] array, int target) {
        for (int i = 0; i < array.length; i++) {
            if (array[i] == target) {
                return i;  // Element gefunden
            }
        }
        return -1;  // Element nicht gefunden
    }
    
    // Binäre Suche - O(log n) - Array muss sortiert sein
    public static int binarySearch(int[] sortedArray, int target) {
        int left = 0;
        int right = sortedArray.length - 1;
        
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (sortedArray[mid] == target) {
                return mid;  // Element gefunden
            } else if (sortedArray[mid] < target) {
                left = mid + 1;  // Rechts weitersuchen
            } else {
                right = mid - 1;  // Links weitersuchen
            }
        }
        
        return -1;  // Element nicht gefunden
    }
    
    // Interpolationssuche - O(log log n) im Durchschnitt
    // Funktioniert nur für gleichmäßig verteilte, sortierte Arrays
    public static int interpolationSearch(int[] sortedArray, int target) {
        int left = 0;
        int right = sortedArray.length - 1;
        
        while (left <= right && target >= sortedArray[left] && target <= sortedArray[right]) {
            if (left == right) {
                return sortedArray[left] == target ? left : -1;
            }
            
            // Interpolationsformel
            int pos = left + ((target - sortedArray[left]) * (right - left)) / 
                        (sortedArray[right] - sortedArray[left]);
            
            if (sortedArray[pos] == target) {
                return pos;
            } else if (sortedArray[pos] < target) {
                left = pos + 1;
            } else {
                right = pos - 1;
            }
        }
        
        return -1;
    }
    
    // Exponentielle Suche - O(log n) für unendlich große Arrays
    public static int exponentialSearch(int[] sortedArray, int target) {
        int n = sortedArray.length;
        
        if (sortedArray[0] == target) {
            return 0;
        }
        
        // Bereich finden, in dem das Element sein könnte
        int i = 1;
        while (i < n && sortedArray[i] <= target) {
            i = i * 2;
        }
        
        // Binäre Suche im gefundenen Bereich
        return binarySearchRange(sortedArray, i / 2, Math.min(i, n - 1), target);
    }
    
    private static int binarySearchRange(int[] array, int left, int right, int target) {
        while (left <= right) {
            int mid = left + (right - left) / 2;
            
            if (array[mid] == target) {
                return mid;
            } else if (array[mid] < target) {
                left = mid + 1;
            } else {
                right = mid - 1;
            }
        }
        return -1;
    }
    
    // Jump Search - O(√n) für sortierte Arrays
    public static int jumpSearch(int[] sortedArray, int target) {
        int n = sortedArray.length;
        int step = (int) Math.sqrt(n);
        int prev = 0;
        
        // Block finden, in dem das Element sein könnte
        while (sortedArray[Math.min(step, n) - 1] < target) {
            prev = step;
            step += (int) Math.sqrt(n);
            if (prev >= n) {
                return -1;
            }
        }
        
        // Lineare Suche im Block
        while (sortedArray[prev] < target) {
            prev++;
            if (prev == Math.min(step, n)) {
                return -1;
            }
        }
        
        if (sortedArray[prev] == target) {
            return prev;
        }
        
        return -1;
    }
    
    // Performance-Vergleich der Suchalgorithmen
    public static void compareSearchAlgorithms() {
        Random random = new Random();
        int[] sizes = {1000, 10000, 100000, 1000000};
        
        System.out.println("=== Suchalgorithmen Performance-Vergleich ===");
        System.out.println("Größe\tLinear\tBinär\tInterpolation\tJump\tExponential");
        
        for (int size : sizes) {
            int[] array = new int[size];
            
            // Sortiertes Array erstellen
            for (int i = 0; i < size; i++) {
                array[i] = i;
            }
            
            // Zufälliges Ziel auswählen
            int target = random.nextInt(size);
            
            // Lineare Suche
            long start = System.nanoTime();
            int linearResult = linearSearch(array, target);
            long linearTime = System.nanoTime() - start;
            
            // Binäre Suche
            start = System.nanoTime();
            int binaryResult = binarySearch(array, target);
            long binaryTime = System.nanoTime() - start;
            
            // Interpolationssuche
            start = System.nanoTime();
            int interpolationResult = interpolationSearch(array, target);
            long interpolationTime = System.nanoTime() - start;
            
            // Jump Search
            start = System.nanoTime();
            int jumpResult = jumpSearch(array, target);
            long jumpTime = System.nanoTime() - start;
            
            // Exponentielle Suche
            start = System.nanoTime();
            int exponentialResult = exponentialSearch(array, target);
            long exponentialTime = System.nanoTime() - start;
            
            System.out.printf("%d\t%d\t%d\t%d\t\t%d\t%d%n",
                             size, linearTime, binaryTime, interpolationTime, jumpTime, exponentialTime);
            
            // Ergebnisse überprüfen
            assert linearResult == target;
            assert binaryResult == target;
            assert interpolationResult == target;
            assert jumpResult == target;
            assert exponentialResult == target;
        }
    }
    
    public static void main(String[] args) {
        // Test-Arrays erstellen
        int[] unsortedArray = {64, 34, 25, 12, 22, 11, 90, 88, 76, 50, 42};
        int[] sortedArray = {11, 12, 22, 25, 34, 42, 50, 64, 76, 88, 90};
        
        System.out.println("=== Suchalgorithmen Demo ===");
        
        // Lineare Suche
        int target = 25;
        int index = linearSearch(unsortedArray, target);
        System.out.println("Lineare Suche: " + target + " gefunden an Index " + index);
        
        // Binäre Suche
        index = binarySearch(sortedArray, target);
        System.out.println("Binäre Suche: " + target + " gefunden an Index " + index);
        
        // Interpolationssuche
        index = interpolationSearch(sortedArray, 76);
        System.out.println("Interpolationssuche: 76 gefunden an Index " + index);
        
        // Jump Search
        index = jumpSearch(sortedArray, 42);
        System.out.println("Jump Search: 42 gefunden an Index " + index);
        
        // Exponentielle Suche
        index = exponentialSearch(sortedArray, 88);
        System.out.println("Exponentielle Suche: 88 gefunden an Index " + index);
        
        // Performance-Vergleich
        compareSearchAlgorithms();
        
        // Suchalgorithmen-Eigenschaften
        printSearchAlgorithmProperties();
    }
    
    private static void printSearchAlgorithmProperties() {
        System.out.println("\n=== Suchalgorithmen Eigenschaften ===");
        
        String[][] algorithms = {
            {"Lineare Suche", "O(n)", "Unsortiert", "Einfach"},
            {"Binäre Suche", "O(log n)", "Sortiert", "Effizient"},
            {"Interpolationssuche", "O(log log n)", "Sortiert, gleichverteilt", "Sehr effizient"},
            {"Jump Search", "O(√n)", "Sortiert", "Gut für große Arrays"},
            {"Exponentielle Suche", "O(log n)", "Sortiert", "Unendliche Arrays"}
        };
        
        System.out.println("Algorithmus\t\tZeitkomplexität\tVoraussetzung\t\tBeschreibung");
        System.out.println("---------\t\t--------------\t--------------\t\t-----------");
        
        for (String[] algo : algorithms) {
            System.out.printf("%-20s\t%-15s\t%-20s\t%s%n", algo[0], algo[1], algo[2], algo[3]);
        }
    }
}

Здесь рассмотрены основные алгоритмы поиска и их характеристики. Линейный поиск работает с любыми массивами, но имеет сложность O(n). Бинарный поиск требует отсортированный массив, но работает за O(log n), что значительно быстрее на больших объёмах данных.

Интерполяционный поиск хорошо справляется с равномерно распределёнными данными, достигая O(log log n) в среднем случае. Jump Search предлагает компромисс между простотой линейного поиска и эффективностью бинарного, работая за O(√n). Экспоненциальный поиск полезен для неограниченных массивов и также имеет логарифмическую сложность.

При выборе алгоритма нужно учитывать размер данных, их распределение и требования к производительности. На маленьких массивах разница может быть незаметна, но при работе с миллионами элементов выбор правильного подхода критичен. Тестирование производительности показывает реальные затраты времени на каждом уровне масштабирования.

3. Алгоритмы сортировки

import java.util.*;

public class Sortieralgorithmen {
    
    // Bubble Sort - O(n²)
    public static void bubbleSort(int[] array) {
        int n = array.length;
        boolean swapped;
        
        for (int i = 0; i < n - 1; i++) {
            swapped = false;
            
            for (int j = 0; j < n - i - 1; j++) {
                if (array[j] > array[j + 1]) {
                    // Обмен элементов
                    int temp = array[j];
                    array[j] = array[j + 1];
                    array[j + 1] = temp;
                    swapped = true;
                }
            }
            
            // Если обменов не было, массив отсортирован
            if (!swapped) {
                break;
            }
        }
    }
    
    // Selection Sort - O(n²)
    public static void selectionSort(int[] array) {
        int n = array.length;
        
        for (int i = 0; i < n - 1; i++) {
            int minIndex = i;
            
            // Поиск минимума в неотсортированной части
            for (int j = i + 1; j < n; j++) {
                if (array[j] < array[minIndex]) {
                    minIndex = j;
                }
            }
            
            // Обмен минимума с текущим элементом
            if (minIndex != i) {
                int temp = array[i];
                array[i] = array[minIndex];
                array[minIndex] = temp;
            }
        }
    }
    
    // Insertion Sort - O(n²) худший случай, O(n) лучший случай
    public static void insertionSort(int[] array) {
        for (int i = 1; i < array.length; i++) {
            int key = array[i];
            int j = i - 1;
            
            // Сдвиг элементов, пока не найдена правильная позиция
            while (j >= 0 && array[j] > key) {
                array[j + 1] = array[j];
                j--;
            }
            
            array[j + 1] = key;
        }
    }
    
    // Quick Sort - O(n log n) среднее, O(n²) худший случай
    public static void quickSort(int[] array) {
        quickSortRecursive(array, 0, array.length - 1);
    }
    
    private static void quickSortRecursive(int[] array, int low, int high) {
        if (low < high) {
            int pivotIndex = partition(array, low, high);
            
            quickSortRecursive(array, low, pivotIndex - 1);
            quickSortRecursive(array, pivotIndex + 1, high);
        }
    }
    
    private static int partition(int[] array, int low, int high) {
        int pivot = array[high];  // Последний элемент как опорный
        int i = (low - 1);  // Индекс меньшего элемента
        
        for (int j = low; j < high; j++) {
            if (array[j] < pivot) {
                i++;
                swap(array, i, j);
            }
        }
        
        swap(array, i + 1, high);
        return i + 1;
    }
    
    private static void swap(int[] array, int i, int j) {
        int temp = array[i];
        array[i] = array[j];
        array[j] = temp;
    }
    
    // Merge Sort - O(n log n)
    public static void mergeSort(int[] array) {
        if (array.length <= 1) {
            return;
        }
        
        int mid = array.length / 2;
        int[] left = Arrays.copyOfRange(array, 0, mid);
        int[] right = Arrays.copyOfRange(array, mid, array.length);
        
        mergeSort(left);
        mergeSort(right);
        
        merge(array, left, right);
    }
    
    private static void merge(int[] result, int[] left, int[] right) {
        int i = 0, j = 0, k = 0;
        
        while (i < left.length && j < right.length) {
            if (left[i] <= right[j]) {
                result[k++] = left[i++];
            } else {
                result[k++] = right[j++];
            }
        }
        
        while (i < left.length) {
            result[k++] = left[i++];
        }
        
        while (j < right.length) {
            result[k++] = right[j++];
        }
    }
    
    // Heap Sort - O(n log n)
    public static void heapSort(int[] array) {
        int n = array.length;
        
        // Построение max-heap
        for (int i = n / 2 - 1; i >= 0; i--) {
            heapify(array, n, i);
        }
        
        // Извлечение элементов из heap
        for (int i = n - 1; i > 0; i--) {
            swap(array, 0, i);
            heapify(array, i, 0);
        }
    }
    
    private static void heapify(int[] array, int n, int i) {
        int largest = i;
        int left = 2 * i + 1;
        int right = 2 * i + 2;
        
        if (left < n && array[left] > array[largest]) {
            largest = left;
        }
        
        if (right < n && array[right] > array[largest]) {
            largest = right;
        }
        
        if (largest != i) {
            swap(array, i, largest);
            heapify(array, n, largest);
        }
    }
    
    // Сравнение производительности алгоритмов сортировки
    public static void compareSortingAlgorithms() {
        Random random = new Random();
        int[] sizes = {1000, 5000, 10000, 20000};
        
        System.out.println("=== Сравнение производительности алгоритмов сортировки ===");
        System.out.println("Размер\tBubble\tSelection\tInsertion\tQuick\tMerge\tHeap");
        
        for (int size : sizes) {
            // Создание тестового массива
            int[] originalArray = new int[size];
            for (int i = 0; i < size; i++) {
                originalArray[i] = random.nextInt(10000);
            }
            
            long[] times = new long[6];
            String[] names = {"Bubble", "Selection", "Insertion", "Quick", "Merge", "Heap"};
            
            // Bubble Sort
            int[] array = originalArray.clone();
            long start = System.nanoTime();
            bubbleSort(array);
            times[0] = System.nanoTime() - start;
            
            // Selection Sort
            array = originalArray.clone();
            start = System.nanoTime();
            selectionSort(array);
            times[1] = System.nanoTime() - start;
            
            // Insertion Sort
            array = originalArray.clone();
            start = System.nanoTime();
            insertionSort(array);
            times[2] = System.nanoTime() - start;
            
            // Quick Sort
            array = originalArray.clone();
            start = System.nanoTime();
            quickSort(array);
            times[3] = System.nanoTime() - start;
            
            // Merge Sort
            array = originalArray.clone();
            start = System.nanoTime();
            mergeSort(array);
            times[4] = System.nanoTime() - start;
            
            // Heap Sort
            array = originalArray.clone();
            start = System.nanoTime();
            heapSort(array);
            times[5] = System.nanoTime() - start;
            
            // Вывод результатов
            System.out.printf("%d", size);
            for (long time : times) {
                System.out.printf("\t%d", time);
            }
            System.out.println();
        }
    }
    
    // Тест устойчивости
    public static void testStability() {
        System.out.println("\n=== Тест устойчивости ===");
        
        // Массив с дубликатами
        int[] array = {5, 2, 8, 5, 1, 9, 3, 5};
        
        System.out.println("Original: " + Arrays.toString(array));
        
        // Bubble Sort (устойчив)
        int[] bubbleArray = array.clone();
        bubbleSort(bubbleArray);
        System.out.println("Bubble Sort: " + Arrays.toString(bubbleArray));
        
        // Quick Sort (неустойчив)
        int[] quickArray = array.clone();
        quickSort(quickArray);
        System.out.println("Quick Sort: " + Arrays.toString(quickArray));
        
        // Merge Sort (устойчив)
        int[] mergeArray = array.clone();
        mergeSort(mergeArray);
        System.out.println("Merge Sort: " + Arrays.toString(mergeArray));
    }
    
    public static void main(String[] args) {
        // Тестовый массив
        int[] array = {64, 34, 25, 12, 22, 11, 90, 88, 76, 50, 42};
        
        System.out.println("=== Демонстрация алгоритмов сортировки ===");
        
        // Bubble Sort
        int[] bubbleArray = array.clone();
        bubbleSort(bubbleArray);
        System.out.println("Bubble Sort: " + Arrays.toString(bubbleArray));
        
        // Selection Sort
        int[] selectionArray = array.clone();
        selectionSort(selectionArray);
        System.out.println("Selection Sort: " + Arrays.toString(selectionArray));
        
        // Insertion Sort
        int[] insertionArray = array.clone();
        insertionSort(insertionArray);
        System.out.println("Insertion Sort: " + Arrays.toString(insertionArray));
        
        // Quick Sort
        int[] quickArray = array.clone();
        quickSort(quickArray);
        System.out.println("Quick Sort: " + Arrays.toString(quickArray));
        
        // Merge Sort
        int[] mergeArray = array.clone();
        mergeSort(mergeArray);
        System.out.println("Merge Sort: " + Arrays.toString(mergeArray));
        
        // Heap Sort
        int[] heapArray = array.clone();
        heapSort(heapArray);
        System.out.println("Heap Sort: " + Arrays.toString(heapArray));
        
        // Сравнение производительности
        compareSortingAlgorithms();
        
        // Тест устойчивости
        testStability();
        
        // Свойства алгоритмов сортировки
        printSortingAlgorithmProperties();
    }
    
    private static void printSortingAlgorithmProperties() {
        System.out.println("\n=== Свойства алгоритмов сортировки ===");
        
        String[][] algorithms = {
            {"Bubble Sort", "O(n²)", "In-place", "Устойчив", "Простой"},
            {"Selection Sort", "O(n²)", "In-place", "Неустойчив", "Простой"},
            {"Insertion Sort", "O(n²)", "In-place", "Устойчив", "Малые массивы"},
            {"Quick Sort", "O(n log n)", "In-place", "Неустойчив", "Быстрый"},
            {"Merge Sort", "O(n log n)", "Out-of-place", "Устойчив", "Надежный"},
            {"Heap Sort", "O(n log n)", "In-place", "Неустойчив", "Гарантированный"}
        };
        
        System.out.println("Алгоритм\t\tВремя\t\tПамять\t\tУстойчивость\tОписание");
        System.out.println("---------\t\t------\t\t-------\t\t-----------\t-----------");
        
        for (String[] algo : algorithms) {
            System.out.printf("%-20s\t%-15s\t%-15s\t%-15s\t%s%n", algo[0], algo[1], algo[2], algo[3], algo[4]);
        }
    }
}

Обзор нотации Big-O

Сложность	Описание	Пример	Рост
O(1)	Константное время	Доступ к элементу массива	1
O(log n)	Логарифмическая	Бинарный поиск	log₂(n)
O(n)	Линейная	Линейный поиск	n
O(n log n)	Линеарифмическая	Merge Sort	n·log(n)
O(n²)	Квадратичная	Bubble Sort	n²
O(2ⁿ)	Экспоненциальная	Рекурсивная Fibonacci	2ⁿ

Сравнение алгоритмов поиска

Алгоритм	Временная сложность	Предусловие	Когда использовать
Linear Search	O(n)	Нет	Маленькие несортированные массивы
Binary Search	O(log n)	Отсортирован	Большие отсортированные массивы
Interpolation	O(log log n)	Отсортирован, равномерно распределён	Числовые данные
Jump Search	O(√n)	Отсортирован	Большие массивы с настраиваемым размером прыжка
Exponential	O(log n)	Отсортирован	Бесконечные массивы

Сравнение алгоритмов сортировки

Алгоритм	Временная сложность	Пространственная сложность	Устойчивый	На месте
Bubble Sort	O(n²)	O(1)	Да	Да
Selection Sort	O(n²)	O(1)	Нет	Да
Insertion Sort	O(n²)	O(1)	Да	Да
Quick Sort	O(n log n)	O(log n)	Нет	Да
Merge Sort	O(n log n)	O(n)	Да	Нет
Heap Sort	O(n log n)	O(1)	Нет	Да

Принципы проектирования алгоритмов

Divide and Conquer

1. Разделение: разбить задачу на более мелкие подзадачи
2. Решение: рекурсивно решить каждую подзадачу
3. Объединение: объединить решения

Примеры: Quick Sort, Merge Sort, Binary Search

Жадные алгоритмы

1. Локально оптимальные решения на каждом шаге
2. Надежда на глобальную оптимальность

Примеры: Dijkstra, Kruskal, Huffman Coding

Динамическое программирование

1. Оптимальная подструктура: перекрывающиеся подзадачи
2. Мемоизация: кеширование промежуточных результатов

Примеры: Fibonacci, Knapsack Problem

Оптимизация производительности

Trade-off между памятью и временем

// Обмениваем память на скорость
public class FibonacciMemoization {
    private static Map<Integer, Long> memo = new HashMap<>();
    
    public static long fibonacci(int n) {
        if (n <= 1) return n;
        
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        
        long result = fibonacci(n - 1) + fibonacci(n - 2);
        memo.put(n, result);
        return result;
    }
}

Ранний выход из цикла

// Оптимизированный линейный поиск с дозорным элементом
public static int optimizedLinearSearch(int[] array, int target) {
    int n = array.length;
    
    // Проверяем последний элемент
    if (array[n - 1] == target) {
        return n - 1;
    }
    
    // Заменяем последний элемент на искомый
    int last = array[n - 1];
    array[n - 1] = target;
    
    int i = 0;
    while (array[i] != target) {
        i++;
    }
    
    // Восстанавливаем исходное значение
    array[n - 1] = last;
    
    return i < n - 1 ? i : -1;
}

Плюсы и минусы

Преимущества анализа алгоритмов

• Прогнозирование производительности: оценка времени выполнения
• Выбор алгоритма: правильный выбор метода решения
• Оптимизация: выявление узких мест
• Масштабируемость: понимание поведения при росте объёма данных

Недостатки

• Теоретические допущения: игнорируют константы
• Практические различия: влияние аппаратного обеспечения
• Сложность анализа: требует математического подхода
• Преждевременная оптимизация: ненужные усложнения

Частые вопросы на собеседованиях

1. В чём различие между Best, Average и Worst Case? Best Case показывает наиболее благоприятный сценарий, Average Case — ожидаемую производительность, Worst Case — самый неудачный путь выполнения.

2. Почему Binary Search имеет O(log n), а не O(n)? На каждом шаге область поиска сокращается вдвое, что даёт логарифмическое ускорение.

3. Когда выбрать Insertion Sort вместо Quick Sort? На маленьких массивах или почти отсортированных данных, где Insertion Sort может достичь O(n).

4. Что означает “на месте” для алгоритмов сортировки? Алгоритм сортирует данные без использования дополнительной памяти, требуя O(1) пространства.

Важные источники

1. https://en.wikipedia.org/wiki/Big_O_notation
2. https://www.geeksforgeeks.org/fundamentals-of-algorithms/
3. https://mitpress.mit.edu/books/introduction-algorithms