Всем привет, я работаю программистом, у меня есть множество заметок по этой теме, и я хотел бы поделиться этим с читателями. Все статьи разделяю на мелкие части для лучшего понимания и вашего удобства.
Как оценивается сложность алгоритмов.
Поначалу было трудно понять, но разобраться можно))
Сложность алгоритма оценивают по количеству операций, выполняемых для достижения результата, из которых состоит этот алгоритм. Есть верхняя и нижняя границы сложности алгоритма, это когда для алгоритма можно подобрать такие входные данные, что он будет работать плохо-долго или быстро-хорошо.
То есть, верхняя граница: максимальное время, которое может занять программа для получения выходных данных, выраженное в размере входных данных (наихудший сценарий).
И нижняя граница : минимальное время, которое потребуется программе для получения выходных данных, выраженное в размере входных данных (наилучший сценарий).
Для оценки сложности алгоритма используется такое понятие как "О-большое", она же "Big-O нотация". Когда-то мне было сложно понять саму суть этого термина, но я выделил основное: Big-O призвана показать, как увеличится количество операций в алгоритм при увеличении размера данных на входе в алгоритм. Вот так!
А на примерах еще проще. Например, O(n^2) - n-размер входных данных, а функция g(n)=n^2 даст представление о сложности алгоритма относительно входных данных. В данном примере при увеличении входных данных количество операций будет возрастать в квадратичной кратности, и рано или поздно настанет момент когда всё начнет глючить!
Вообще есть такое правило, что простые решения можно оценивать по количеству вложенных циклов. То есть один цикл это O(n), если в каждом цикле еще по циклу то это O(n^2), если еще и в этих вложенных циклах еще по одному циклу, то это O(n^3) и так далее. Здесь пример - мы выполняем обход элементов массива, где первый пример это массив, второй пример это двумерный массив, и потом трехмерный массив.
В следующей статье я продолжу эту тему, и приведу примеры.
Спасибо за то, что дочитали. Подписывайтеь на мой канал. До встречи!