> Что такое временная сложность алгоритмов и как она измеряется (Go)

Короткий ответ

Временная сложность алгоритмов показывает, как растёт время выполнения при увеличении размера входных данных. Она измеряется в асимптотической нотации, чаще всего Big O, которая описывает верхнюю границу роста. Константы и младшие члены отбрасываются, потому что важна тенденция, а не точные миллисекунды. Для backend на Go это помогает выбирать структуры данных и оценивать, выдержит ли сервис нагрузку.

Подход к решению

Сначала нужно определить, что считать размером входа: длину слайса, число записей в базе или количество запросов. Затем считаем, сколько элементарных операций выполняется в худшем случае. После этого оставляем только самый быстрорастущий член и убираем коэффициенты. Например, если алгоритм делает 3n + 5 операций, сложность будет O(n). Если внутри цикла по n есть вложенный цикл по n, получаем O(n²). Для рекурсивных алгоритмов удобно использовать рекуррентные соотношения или мастер-теорему. На практике также важно различать average case и worst case, потому что хеш-таблицы в среднем дают O(1), но в худшем случае могут деградировать до O(n).

Пример кода

GO
package main

import "fmt"

// O(n) - линейный поиск
func linearSearch(nums []int, target int) int {
    for i, v := range nums {
        if v == target {
            return i
        }
    }
    return -1
}

// O(n^2) - проверка дубликатов наивным способом
func hasDuplicatesSlow(nums []int) bool {
    for i := 0; i < len(nums); i++ {
        for j := i + 1; j < len(nums); j++ {
            if nums[i] == nums[j] {
                return true
            }
        }
    }
    return false
}

// O(n) в среднем - проверка дубликатов через map
func hasDuplicatesFast(nums []int) bool {
    seen := make(map[int]struct{}, len(nums))
    for _, v := range nums {
        if _, ok := seen[v]; ok {
            return true
        }
        seen[v] = struct{}{}
    }
    return false
}

func main() {
    nums := []int{1, 2, 3, 4, 5}
    fmt.Println(linearSearch(nums, 3)) // 2
    fmt.Println(hasDuplicatesSlow(nums)) // false
    fmt.Println(hasDuplicatesFast(nums)) // false
}

Edge cases

Пустой вход часто даёт O(1), потому что цикл не выполняется. Один элемент тоже может быть вырожденным случаем. Для алгоритмов с логарифмической сложностью важно, чтобы данные были отсортированы или структура поддерживала деление пополам. В Go нужно помнить, что операции с map и slice имеют свои особенности: доступ к slice по индексу - O(1), а вставка в середину slice - O(n). Также стоит учитывать, что константы могут быть настолько большими, что асимптотически лучший алгоритм проигрывает на малых данных.

Как отвечать на собеседовании

Скажите, что временная сложность - это функция от размера входа, описывающая рост числа операций. Объясните, что Big O показывает верхнюю границу и позволяет сравнивать алгоритмы независимо от железа. Приведите пример: линейный поиск - O(n), бинарный поиск - O(log n), вложенные циклы - O(n²). Упомяните, что на практике важно учитывать average case и worst case. Если спросят про Go, добавьте, что slice и map имеют разные характеристики, и это влияет на выбор решения.

Что проверяет интервьюер

Понимание базовой теории алгоритмов и умение применять её к реальному коду. Способность оценить сложность простого цикла, вложенного цикла и рекурсии. Знание различий между O(1), O(log n), O(n), O(n log n) и O(n²). Умение объяснить, почему константы отбрасываются. Взвешенность суждений: кандидат не должен фанатично оптимизировать там, где это не нужно, но должен видеть потенциальные проблемы на больших данных.