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