Что такое сложность алгоритма — пример ответа на собеседовании Android Разработчик

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

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

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

Ответ

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

Основные виды:

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

// O(n) – линейный поиск
fun linearSearch(list: List<Int>, target: Int): Int? {
    for (i in list.indices) {
        if (list[i] == target) return i
    }
    return null
}

Нюансы: