[Это моя интерпретация / разбивка раздела в CLRS. Это что-то новое, я думаю попробовать, так как у меня есть свободное время. Я собираюсь пройтись по каждому разделу и обобщить как можно больше, работая над несколькими примерами в процессе. Это может быть хороший ресурс для людей, которым нравится разбирать информацию на мелкие кусочки.]

Анализ алгоритмов включает в себя поиск ресурсов, которые необходимы алгоритму, которые в большинстве случаев относятся к времени. Проще говоря:

Анализ алгоритма - это оценка вычислительного времени (или ресурсов в целом), необходимого для выполнения определенного алгоритма, решающего определенную проблему.

Теперь вопрос в том, как именно анализировать алгоритм? На большинстве курсов студенты анализируют результаты с помощью проверки зрения. На самом деле проверка зрения сводится к тому, чтобы посмотреть, сколько циклов содержится в функции и сколько раз вы повторяете n элементов. Это хороший способ проанализировать большинство алгоритмов, не использующих принцип «разделяй и властвуй». Единственным недостатком этого подхода является то, что вы ограничиваетесь рассмотрением только сценариев наихудшего случая. Иногда все работает в нашу пользу, поэтому стоит знать, как подготовиться к каждому случаю алгоритма, чтобы мы могли сравнивать множество различных возможностей друг с другом в зависимости от типа данных, которые нам предоставляются.

Давайте посмотрим на алгоритм:

//Insertion-Sort Algorithm. Using Golang
​
func insertion_sort(arr []int){
  for j := 1; j < len(arr); j++ {
    key := arr[j]
    i := j - 1
    
    for i >= 0 && arr[i] > key {
      arr[i + 1] = arr[i]
      i = i - 1
    }
    arr[i + 1] = key
  }
}

Построчная разбивка алгоритма

func insertion_sort(arr []int) {...}

Эта строка - объявление функции. arr []int - это параметр, который говорит, что эта функция запрашивает slice. В Go slice - это просто указатель на массив. Тип slice предоставляет доступ к изменяемому массиву, что упрощает весь этот процесс. Если бы мы не использовали изменяемый массив, нам пришлось бы объявить и инициализировать новый массив внутри функции, то есть точную копию массива, отправленного нам в качестве аргумента, а затем вернуть вновь созданный массив после того, как мы закончили сортировку .

for j := 1; j < len(arr); j++ {...}

Это начало нашего for-loop. В Go вы можете выполнить быстрое объявление + инициализацию переменной с помощью оператора :=. Итак, j := это то же самое, что int j; j = 1. Мы устанавливаем j в 1, потому что мы собираемся начать процесс со 2-го места (1-й индекс) в массиве. Мы проверяем, меньше ли j длины массива, и если да, то запускаем цикл. Если нет, то мы прекращаем работу.

key := arr[j]

Мы создаем новую переменную с именем key, которая будет содержать текущее место (current index), в котором мы находимся. Если у нас есть массив arr = []int{3, 4, 5, 1, 6}, тогда key = 4 при первом запуске этого цикла.

i := j - 1

Затем мы инициализируем другую переменную с именем i, которая будет отслеживать индексы. Мы устанавливаем это значение на 1 меньше, чем текущая позиция, потому что мы собираемся перейти от current index до 0th index и проверить, какие значения в этом диапазоне больше, чем значение в нашем current index.

for i >=0 && arr[i] > key { ... }

В Go нет while-loop. Вместо этого у вас есть только for-loop минус этап инициализации и итерации, поэтому в основном for-loop, который только содержит условие. Это говорит о том, что пока индекс i не выходит за пределы начала нашего массива, а предыдущее значение все еще больше нашего current index, продолжайте выполнение цикла.

arr[i + 1] = arr[i]

Пока условие цикла истинно (пока мы нашли значения в диапазоне ([0th index: current index]), поменяйте местами значение индекса i + 1 и значение перед ним на i.

i = i - 1

После обмена уменьшите значение i, чтобы мы переместились вниз с current index на 0th index.

arr[i + 1] = key

Затем, как только мы либо а) достигли самого начала массива, либо б) нашли значение, которое не превышает нашего key, мы помещаем наш key в индекс после индекса, который мы в данный момент проверили. .

Когда дело доходит до анализа этого алгоритма, нам нужно кое-что предположить. Предположим, что для компиляции каждой строки / шага кода требуется c времени, где c - константа. Это означает, что обе эти строки теоретически потребуют одинакового времени для компиляции, если запускаются по отдельности:

i = i - 1 /* Takes c time to compile */
​
arr[i + 1] = key /* Also takes c time to compile */

Теперь, когда мы знаем, что каждая строка / шаг стоит нам c постоянного времени, мы должны знать, сколько раз или, лучше сказать, как часто мы запускаем каждую строку, чтобы что мы можем определить общую стоимость алгоритма. Проще говоря:

Cost of Step = Cost of line * Number of Times We Run that Line

И

Cost of Algorithm = Summation of Cost of each Step

Авария

for j := 1; j < len(arr); j++

Эта строка выполняется n раз. Причина в том, что вы начинаете с индекса 1 и выполняете до тех пор, пока не будет запущено len (arr) which = n для всего n-1, но вам нужно выполнить одну дополнительную проверку, чтобы знать, как завершить цикл, который оставляет ты с n - 1 + 1 = n бегаешь. Постоянное время для этого будет обозначено c1.

key = arr[j]
i = j-1

Эти две строки выполняются n-1 раз, а не n раз, как первая строка, просто потому, что первая строка должна проверить одну больше времени, чтобы знать, когда завершить. Постоянным временем для этих прогонов будет c2 и c4.

for i > 0 && arr[i] > key {...}

Эта часть становится сложной. Мы не знаем точно, сколько раз это while-loop запускается, поскольку оно может варьироваться в зависимости от массива, поэтому нам нужен новый идентификатор для того, как часто while-loop запускается, и мы назовем его tj.

tj просто указывает, сколько раз выполняется цикл. Например, 1-й цикл может выполняться всего t1 = 2 раза, а 2-й цикл может выполняться для t2 = 4. Таким образом, эта строка выполняется несколько раз, пока следующие строки:

arr[i + 1] = arr[i]
i = i - 1

Выполнить всего tj- 1 раза, потому что не выполняется дополнительное время, необходимое для проверки условия. Константы для этих трех строк будут c5, c6 и c7.

arr[i + 1] = key

Выполняется в общей сложности n - 1 раз. Константа для этой строки будет c8.

Общее время работы

​

Допустим, мы оцениваем T(n) как лучшее время работы. В лучшем случае это будет означать, что массив, который мы хотим отсортировать, уже отсортирован. Если это так, то нам ни в коем случае не нужно запускать цикл while, это означает, что все значения tj будут равны 0, а наивысший порядок нашей полиномиальной функции будет равен 1, поэтому наш полином будет выглядеть примерно так. к:

​

В худшем случае мы будем сортировать массив в обратном порядке. Это означает, что каждый цикл while должен выполняться максимальное количество раз (tj = j в суммировании), и нам действительно нужно будет решить T(n) выше, чтобы узнать, какой член является наивысшим. Это можно сделать путем осмотра (и немного веры).

Возьмите термин:

Если бы мы расширили это, мы получили бы следующее:

​

Если это наихудший сценарий, то и. Это имеет смысл, поскольку внутренний цикл while, в худшем случае, в самом конце массива, должен переместить наименьшее значение (поскольку массив находится в обратном порядке) до самого начала массива. Также помните, что каждый представляет собой линию / шаг. Это означает, что цикл while выполняется [(n * (n + 1)) / 2] раз. Например, массив из 6 элементов,

Это означает, что условие цикла while выполняется всего 21 раз в наихудшем сценарии. Это можно проверить с помощью следующего кода:

package main
​
import "fmt"
​
func insertion_sort(arr []int) {
    for j := 1; j < len(arr); j++ {
    key := arr[j]
    i := j - 1
    
    count := 0
    sum := 0
    for i >= 0 && arr[i] > key {
        count += 1
        sum += count
        arr[i + 1] = arr[i]
        i = i - 1
    }
    /* this makes sure to take into consideration
    the extra check on the for-loop for termination*/
    count +=1
    sum += count
    fmt.Printf("This is the %d run\n", sum)
​
    arr[i + 1] = key
  }
}
​
func main() {
    arr := []int{6, 5, 4, 3, 2, 1}
    fmt.Printf("Here's our array: %v\n", arr)
    insertion_sort(arr)
    fmt.Printf("Here's our sorted array: %v\n", arr)
}

Зная, что наш самый высокий член в полиноме имеет степень 2, мы знаем, что форма T(n) будет квадратичной для худшего сценария:

​

Этот алгоритм также является линейным в лучшем случае:

​

Время работы для наихудшего случая, известное как Big-O notation.

Эта нотация будет обсуждаться далее в другой статье, но то, что она означает здесь, дается алгоритму, например insertion sort, если бы мы должны были протестировать его на различных размерах n, то его форма в координатной плоскости выглядела бы так квадратичная функция, основанная на функции T(n), которую мы вывели ранее.

Просто взглянуть на эту информацию, имея за плечами один алгоритм, мало что значит. Как только вы начнете сравнивать время работы, вы поймете важность уравнений.