Какова сложность доступа к элементу массива/слайса по индексу и поиска по значению?

Ответ

В Go, как и в большинстве языков, операции с массивами и слайсами имеют разную сложность в зависимости от задачи.

1. Доступ по индексу: O(1)

Доступ к элементу по его индексу (например, mySlice[5]) имеет константную сложность O(1).

Это возможно потому, что элементы массива (или нижележащего массива слайса) хранятся в памяти в виде непрерывного блока. Зная начальный адрес массива и размер элемента, можно мгновенно вычислить адрес нужного элемента по формуле: начальный_адрес + индекс * размер_элемента.

// Массив или слайс
items := []string{"a", "b", "c", "d", "e"}

// Доступ по индексу - O(1)
element := items[2] // Моментальный доступ к "c"
fmt.Println(element)

2. Поиск по значению: O(n)

Поиск определённого значения в несортированном массиве или слайсе требует перебора элементов один за другим. Эта операция имеет линейную сложность O(n).

В худшем случае (элемент последний или отсутствует) придётся проверить все n элементов.

func findIndex(items []string, value string) int {
    // Линейный поиск - O(n)
    for i, v := range items {
        if v == value {
            return i // Элемент найден, возвращаем индекс
        }
    }
    return -1 // Элемент не найден
}

index := findIndex(items, "d") // В худшем случае пройдём весь слайс
fmt.Println(index) // 3