Как оценить насколько быстрая написанная нами программа? Как оценить скорость программы?

Измерить временной шкалой? Минуты, секунды и милисекунды? Но в таком случае одна и та же программа на разных компьютерах будет показывать разные результаты.

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

Представим сложность алгоритма как некую зависимость от количества входных данных - n. Тогда мы можем записать примерные виды сложности алгоритмов:

534*n³ + 16*n² + 256

2n⁴ + 10

Какой из этих алгоритмов быстрее работает?

Для оценки мы берем только наихудщие случаи с точностью до коэффициента. Представим что n стремится к большому числу. В таком случает понятно, что константы не играют болшой роли. И в практике оценки алгоритма принято брать только худшие слагаемые. Худшие имеются ввиду те, что быстрее всех растет. Если входные данные небольшие, то они быстро работают при любых алгоритмах и нет необходимости. Таким образом мы приходим к таким упрощениям:

n³

n⁴

 Видно, что второй алгоритм дольше работает чем первый. Конечно, это все теоретически. В теории мы берем максимально большие числа. А на практике нужно исходить от тех исходных данных которые есть или которые могут быть.

Бинарный поиск - это алгоритм, который на входе получает отсортированный список элеменитов. Если элемент, который вы ищете, присутствует в списке,
то бинарный поиск возвращает ту позицию, в которой он был найден. В противном случае бинарный поиск возвращает null. При бинарном поиске каждый раз исключается половина элементов.

Алгоритмы сортировки упорядочивают элементы по определённому критерию.

Сортировка вставками

В алгоритме Insertion sort элементы входной последовательности просматриваются по одному, и каждый новый поступивший элемент размещается в подходящее место среди ранее упорядоченных элементов.

В первой итерации внешнего цикла будет только один цикл внутреннего, во втором цикле будет 2 внутренних цикла т.е с ростом количества циклов растет и количество внутреннего цикла.

Временная сложность алгоритма — O(n²)

Граф — абстрактный математический объект, представляющий собой множество вершин графа и набор рёбер, то есть соединений между парами вершин.

Такое определение у графа в википедии. Простыми словами это набор точек и линий которые связывают точки. Граф моделирует набор связей между разными объектами и каждый граф состоит из узлов и ребер. Узел может быть напрямую соединен с несколькими другими узлами. Эти узлы называются соседями.

Поиск в ширину позволяет найти кратчайшее рассторяние между двумя объектами. Кратчайший в данном случае это количество шагов, состояний или изменений.

Например, с помощью поиска в ширину можно:

- написать программу для игры в шашки, которая вычисляет кратчайший путь к победе;

- реализовать проверку правописания (минимальное количество изменений, чтобы поправить ошибку);

- найти ближайшего врача;

- добраться до определенного места минимальным количеством пересадок;

Алгоритм Дейкстры - алгоритм на графах, изобретённый нидерландским учёным Эдсгером Дейкстрой в 1959 году. Находит кратчайшие пути от одной из вершин графа до всех остальных. 

Если поиск в ширину позволяет найти путь с минимальным количеством пересадок из точки А в точку В, то алгоритм Дейкстры позволяет найти самый быстрый путь из точки А в точку В. 

Когда работаете с алгоритмом Дейкстры, с каждым ребром графа связывается число, называемое весом. Алгоритм Дейкстры работает с взвешенным графом и только с направленными ациклическими графами, которые нередко обозначаются сокращением DAG (Directed Acyclic Graph). Таким образом граф должен быть взвешенным, направленным и без циклов. 

Граф с весами называется взвешенным графом.