Ответ
В 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