Что такое алгоритмическая сложность

«Что такое алгоритмическая сложность» — вопрос из категории Алгоритмы и структуры данных, который задают на 28% собеседований C# Разработчик. Ниже — развёрнутый ответ с разбором ключевых моментов.

Тип вопроса: Алгоритмы и структуры данных Вероятность: 28% Категория: C# Разработчик

Ответ

Алгоритмическая сложность (O-нотация) описывает, как быстро растёт время выполнения или потребление памяти алгоритма при увеличении размера входных данных.

Основные виды сложности:

O(1) – константная (доступ к элементу массива).
O(log n) – логарифмическая (бинарный поиск).
O(n) – линейная (поиск в неотсортированном массиве).
O(n log n) – линейно-логарифмическая (быстрая сортировка).
O(n²) – квадратичная (пузырьковая сортировка).

Пример:

// O(n) – линейная сложность  
int SumArray(int[] arr)  
{  
    int sum = 0;  
    foreach (int num in arr)  // Проход по всем элементам  
        sum += num;  
    return sum;  
}

Чем больше элементов в arr, тем дольше выполнение.