Пока писал предыдущую статью понял, что несколько раз упомянул в ней такую штуку, как «сложность алгоритма». Спустя пару ночей пришел к выводу, что оно тянет на отдельную статью... В общем, так и получилось.
Как и в прошлый раз, чтобы не копировать тексты, вкратце расскажу, о чем там речь.
Сначала рассмотрена теория, что такое эта самая сложность алгоритма и для чего она нужна. Если вкратце — это время. Абстрактное время выполнения алгоритма. Зависит оно от реализации этого алгоритма (ну и от железа, на котором выполняется, но в силу абстрактности это можно опустить).
Обозначается она большой буквой О и может принимать разные значения. Например:
Далее практическая часть, в рамках которой я допилил в предыдущую программу функцию простого поиска по массиву перебором:
Также я прикрутил к функциям счетчик времени выполнения каждой из них и потестировал. Результаты тестов на входных массивах различной длины были сведены в наглядную табличку, показывающую, что при переступании порога в 1000 элементов бинарный поиск начинает резко вырываться вперед, а на больших размерах массивов разница по времени составляет более 600 раз.
Сама табличка:
![[Изображение: Screenshot_20220905_210402.png]](https://blog.zhbert.ru/wp-content/uploads/2022/09/Screenshot_20220905_210402.png)
Как и в прошлый раз, чтобы не копировать тексты, вкратце расскажу, о чем там речь.
Сначала рассмотрена теория, что такое эта самая сложность алгоритма и для чего она нужна. Если вкратце — это время. Абстрактное время выполнения алгоритма. Зависит оно от реализации этого алгоритма (ну и от железа, на котором выполняется, но в силу абстрактности это можно опустить).
Обозначается она большой буквой О и может принимать разные значения. Например:
- O(n) — линейное время;
- O(log n) — логарифмическое время;
- O(n * log n) — линейное, помноженное на логарифмическое для каждой итерации;
- O(n2) — линейное в квадрате;
- O(n!) — факториальное, стремящееся к бесконечности.
Далее практическая часть, в рамках которой я допилил в предыдущую программу функцию простого поиска по массиву перебором:
Код:
func simpleSearch(array *[]int, lookingFor int) (int, bool) {
count := 0
start := time.Now()
for value := range *array {
count++
if value == lookingFor {
duration := time.Since(start)
fmt.Print("Simple search time: ")
fmt.Println(duration)
fmt.Println("Steps: " + strconv.Itoa(count))
return value, true
}
}
duration := time.Since(start)
fmt.Print("Simple search time: ")
fmt.Println(duration)
fmt.Println("Steps: " + strconv.Itoa(count))
return 0, false
}Также я прикрутил к функциям счетчик времени выполнения каждой из них и потестировал. Результаты тестов на входных массивах различной длины были сведены в наглядную табличку, показывающую, что при переступании порога в 1000 элементов бинарный поиск начинает резко вырываться вперед, а на больших размерах массивов разница по времени составляет более 600 раз.
Сама табличка:
За подробностями и болтологией прошу сюда. Ну и как всегда рад любым комментам.
