O большое показывает скорость выполнения в худшем случае.
- Бинарный поиск - Логарифмическое время
O(log n) - Линейный поиск -
O(n) - Быстрая сортировка - Эффективный алгоритмы сортировки
O( n * log n) - Сортировка выбором - Медленные алгоритмы сортировки
O(n * n )n в квадрате. - Перебор всех возможных вариантов - Очень медленный алгоритм
O(n!)
Отображение выполнения алгоритмов на графике.
Вычисли́тельная сло́жность ( Асимптотическая сложность ) — понятие в информатике и теории алгоритмов, обозначающее функцию зависимости объёма работы, которая выполняется некоторым алгоритмом, от размера входных данных. Раздел, изучающий вычислительную
Допустим, некоторому алгоритму нужно выполнить 4n^3 + 7n условных
операций, чтобы обработать n элементов входных данных. При
увеличении n на итоговое время работы будет значительно больше
влиять возведение n в куб, чем умножение его на 4 или же
прибавление 7n. Тогда говорят, что временная сложность этого
алгоритма равна О(n3), т. е. зависит от размера входных
данных кубически.
Примеры сложности алгоритмов:
-
O(n) — линейная сложность.
Такой сложностью обладает, например, алгоритм поиска наибольшего элемента в не отсортированном массиве. Нам придётся пройтись по всем n элементам массива, чтобы понять, какой из них максимальный.
-
O(log n) — логарифмическая сложность.
Простейший пример — бинарный поиск. Если массив отсортирован, мы можем проверить, есть ли в нём какое-то конкретное значение, методом деления пополам. Проверим средний элемент, если он больше искомого, то отбросим вторую половину массива — там его точно нет. Если же меньше, то наоборот — отбросим начальную половину. И так будем продолжать делить пополам, в итоге проверим log n элементов.
-
O(n2) — квадратичная сложность.
Такую сложность имеет, например, алгоритм сортировки вставками. В канонической реализации он представляет собой два вложенных цикла: один, чтобы проходить по всему массиву, а второй, чтобы находить место очередному элементу в уже отсортированной части. Таким образом, количество операций будет зависеть от размера массива как n * n, т. е. n2.
Как работает память
Память в ПК работает так как большой ящик, с адресованными ячейками памяти. feOffeeb - типичный адрес ячейки памяти. Именно такие ячейки памяти выделяются в языке С++ при обьявлении переменных, но до присвоения им какого либо значения. то есть в ячейке памяти находится всякий мусор.
Массивы и связанные списки
Для сохранения некоторого количества связанных между собой элементов, используется либо списки, либо массивы.
Массивы
Массивы - при сохранении массивов все элементы массива записываются в памяти один за другим непосредственно, прямо в соседних ячейках памяти.
Но при желании добавить еще один элемент в массив, мы встречаемся с проблемой, следующей ячейке уже лежат другие значения, встречая такую ситуацию компьютер ищет другое место в памяти, где есть нужное количество незанятых ячеек памяти, и после этого полность переносит весь массив с добавлением новых значений в этот блок памяти.
Таким образом добавление элементов в массив сильно замедляет работу, в таких языках как: PHP, JavaScript, Python в которых есть динамические массивы, все, так и работает. Такие языки как С++ имеют как динамические массивы так и статические, со строго фиксированным количеством мест в массиве, что позволяет не перемещать массив при добавлении нового элемента, но ограничивают работу, от использования динамических массивов никуда не уйти, они необходимы.
Нельзя просто забронировать 10 мест под массив, если в массив попадет всего 3 элемента то остальные не будут исп эфективно, а если потребуется вставить более 10 элементов, перемещать все равно придется.
Для решения этой проблемы используется не массивы, а списки.
Списки - При использовании списков, элементы могут размещаться где угодно в памяти,
Таким образом решается проблема хранения и добавления элементов, но возникает вопрос как связать эти элементы воедино, так чтобы мы знали что данные лежащие в совершенно разных местах памяти обледенены в единый список.
Это решается тем что все эти элементы связываются ссылками, каждый элемент из списка хранит в себе помимо самих своих данных еще и ссылку на адрес в памяти хранения другого элемента.
Таким образом мы получаем цепочку элементов, называемых связанным списком.
Массивы хоть и не могут удобно добавлять данные, но благодаря тому что мы знаем место хранения каждого элемента в массиве, мы способны быстро получать любой нужный произвольный элемент в массиве в любой момент, то преимущество массивов.
В списках мы не можем получить нужный произвольный элемент сразу же нам приходится последовательно пройтись по всем элементам списка, чтобы дойти до нужного. Списки легко вставляю данные, но плохо их изымают из памяти, использовать списки следует в случаях когда требуется последовательной пройтись по всем элементам списка.
Таким образом получаем следующую картину.
Предположим что мы хотим вставить в Массив новый элемент и вставить его в середину массива, таким образом нам придется сдвинуть все элементы идущие после той позиции в которую мы вставляем значение.
При вставке элемента в список, мы просто сдвигаем указатель, так образ это происходит быстро и легко.
Тут в отношении со списками все также, массивами почти также, при вставке в массив мы не просто сдвигаем все остальные элементы, но и при недостатке места, переносим весь массив, при удалении же мы просто сдвигаем все элементы с той позиции в которую вставляем элемент.