Сложность алгоритмов на примере сравнения бинарного и простого поисков на Golang
#1
Пока писал предыдущую статью понял, что несколько раз упомянул в ней такую штуку, как «сложность алгоритма». Спустя пару ночей пришел к выводу, что оно тянет на отдельную статью... В общем, так и получилось.

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

Сначала рассмотрена теория, что такое эта самая сложность алгоритма и для чего она нужна. Если вкратце — это время. Абстрактное время выполнения алгоритма. Зависит оно от реализации этого алгоритма (ну и от железа, на котором выполняется, но в силу абстрактности это можно опустить).

Обозначается она большой буквой О и может принимать разные значения. Например:
  • 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 раз.

Сама табличка:

[Изображение: Screenshot_20220905_210402.png]
За подробностями и болтологией прошу сюда. Ну и как всегда рад любым комментам.
#2
Ничего не понятно, но очень интересно. Может потому-что я не силен в этой вашей тригонометрии
Возможно похожие темы ...
Тема
Автор
  /  
Последний пост

Перейти к форуму:

Пользователи, просматривающие эту тему: 1 Гость(ей)