Алгоритм имеет логарифмическую сложность O(log N). Сколько примерно операций он выполнит для 100 элементов?

Ответ

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

Для n = 100 элементов, количество операций будет примерно равно логарифму по основанию 2 от 100:

log₂(100) ≈ 6.64

В реальных алгоритмах, таких как бинарный поиск, количество шагов — это целое число. Поэтому потребуется 7 операций (округление вверх).

Наглядный пример роста:

Количество элементов (n)	Примерное число операций (log₂ n)
8	3
100	7
1,000	10
1,000,000	20

Пример на Go (бинарный поиск):

// binarySearch ищет target в отсортированном срезе arr
// и возвращает количество выполненных итераций.
func binarySearch(arr []int, target int) int {
    low, high := 0, len(arr)-1
    steps := 0
    for low <= high {
        steps++ // Считаем итерацию
        mid := low + (high-low)/2 // Безопасный способ избежать переполнения

        if arr[mid] == target {
            return steps
        } else if arr[mid] < target {
            low = mid + 1
        } else {
            high = mid - 1
        }
    }
    return steps // Возвращаем шаги, даже если элемент не найден
}

// Для отсортированного массива из 100 элементов
// функция вернет максимальное значение 7.