Один шаг при любом размере
O(1) означает константное время: операция выполняется за одно и то же число шагов, независимо от того, содержит вход 5 элементов или миллион. Объём работы не растёт вообще.
Это лучшая сложность, которая бывает. Типичные операции O(1) в Go: чтение элемента среза по индексу, чтение значения из map по ключу, len(), добавление одного элемента и простая арифметика.
Обратите внимание, чего O(1) не означает: это не значит «быстро», это значит «не становится медленнее при росте входных данных». Один константный шаг всё ещё может быть медленным — но он остаётся одним шагом.
Поиск в срезе и в map
Элемент среза лежит в известном месте памяти, поэтому words[2] — это один переход: компьютер не проходит по элементам, стоящим перед ним. Такое же чтение стоит столько же и в срезе из миллиона элементов.
Поиск в map вида ages["Ben"] тоже в среднем занимает константное время: ключ прямо указывает map, где хранится значение. Поиск возвращает value, ok, и ok равно false, когда ключа нет.
Чтение элемента по индексу
Программа читает один элемент из среза из 5 элементов и один — из среза с миллионом элементов. Оба чтения — это один шаг: длина среза не играет роли.
Вывод: программа на Go и захваченный вывод
package main
import "fmt"
func main() {
words := []string{"one", "two", "three", "four", "five"}
big := make([]int, 1000000)
for i := range big {
big[i] = i * 2
}
// По одному шагу в каждом случае, какой бы длины ни был срез.
fmt.Println(words[2])
fmt.Println(big[999999])
}
Чтение значения по ключу
ages["Ben"] находит 25 напрямую. Отсутствующий ключ "Dan" возвращает нулевое значение 0 и ok == false — всё так же за константное время.
Вывод: программа на Go и захваченный вывод
package main
import "fmt"
func main() {
ages := map[string]int{"Ana": 30, "Ben": 25, "Cleo": 41}
age, ok := ages["Ben"]
fmt.Println(age, ok)
age, ok = ages["Dan"]
fmt.Println(age, ok)
}
Добавление элемента и простая арифметика
append() добавляет один элемент в конец среза. Чаще всего это один шаг. (Изредка срез приходится увеличивать, и он копируется, но в среднем стоимость одного append остаётся константной.)
Все мелкие операции — присваивания, сложения, сравнения, обмен двух значений — тоже O(1). Это те самые «шаги», в которых считаются все остальные классы сложности.
Добавление одного элемента
append() помещает "жёлтый" в конец. Стоимость не зависит от того, сколько цветов уже есть в срезе.
Вывод: программа на Go и захваченный вывод
package main
import "fmt"
func main() {
colors := []string{"красный", "зелёный", "синий"}
fmt.Println("до: ", colors, "длина:", len(colors))
colors = append(colors, "жёлтый")
fmt.Println("после:", colors, "длина:", len(colors))
}
Обмен двух значений
a, b = b, a меняет местами два значения за один шаг константного времени — вспомогательная переменная не нужна.
Вывод: программа на Go и захваченный вывод
package main
import "fmt"
func main() {
a, b := 1, 2
fmt.Println("до: ", a, b)
a, b = b, a
fmt.Println("после:", a, b)
}