Один проход по данным
O(n) означает линейное время: объём работы растёт вместе с размером входных данных. Вдвое больше элементов — вдвое больше шагов.
В Go линейное время обычно выглядит как один цикл for по срезу или по map. Любой алгоритм, которому нужно хотя бы посмотреть на каждый элемент — суммирование, подсчёт, поиск в неотсортированном срезе, — не может быть быстрее, чем O(n).
Линейное время — хорошая сложность. Миллионы элементов не проблема для одного прохода.
Линейный поиск
Если срез не отсортирован, единственный способ найти значение — проверять элементы по очереди, начиная с первого. Это линейный поиск.
В худшем случае — значение стоит последним или его вообще нет — цикл посетит все n элементов. Именно этот худший случай и описывает O(n).
Найти значение и его позицию
Цикл проверяет "one", "two", "three", прежде чем дойти до "four" — 4 шага для совпадения по индексу 3. break останавливает цикл, как только значение найдено.
Вывод: программа на Go и захваченный вывод
package main
import "fmt"
func main() {
words := []string{"one", "two", "three", "four", "five"}
steps := 0
for i, w := range words {
steps++
if w == "four" {
fmt.Println("найдено по индексу", i, "за", steps, "шага")
break
}
}
}
Обход каждого элемента
Многие повседневные задачи — это один проход по всему срезу: сложить все значения, запомнить наибольшее из встреченных, посчитать элементы, проходящие проверку. Каждый элемент затрагивается ровно один раз, поэтому все они O(n).
Два или три таких прохода подряд — всё ещё линейное время: O(2n) и O(3n) сводятся к O(n).
Сумма всех элементов
Цикл добавляет каждый элемент к sum. 8 элементов, 8 сложений — классический вид одного прохода.
Вывод: программа на Go и захваченный вывод
package main
import "fmt"
func main() {
nums := []int{3, 1, 4, 1, 5, 9, 2, 6}
sum := 0
for _, n := range nums {
sum += n
}
fmt.Println("сумма", len(nums), "элементов:", sum)
}
Найти наибольшее значение
max вначале равен первому элементу; каждый следующий элемент, который больше, заменяет его. После одного прохода остаётся наибольшее значение — 9.
Вывод: программа на Go и захваченный вывод
package main
import "fmt"
func main() {
nums := []int{3, 1, 4, 1, 5, 9, 2, 6}
max := nums[0]
for _, n := range nums[1:] {
if n > max {
max = n
}
}
fmt.Println("наибольшее значение:", max)
}
Подсчёт совпадений
Цикл проверяет каждое слово условием len(w) > 3 и считает подходящие. Три слова длиннее 3 букв.
Вывод: программа на Go и захваченный вывод
package main
import "fmt"
func main() {
words := []string{"one", "two", "three", "four", "five"}
count := 0
for _, w := range words {
if len(w) > 3 {
count++
}
}
fmt.Println(count, "слова длиннее 3 букв")
}