Всем привет, я работаю программистом, у меня есть множество заметок по этой теме, и я хотел бы поделиться этим с читателями. Все статьи разделяю на мелкие части для лучшего понимания и вашего удобства. Я буду очень рад если эта информация будет вам полезна.
Программирование простыми словами. Как оценивается сложность алгоритмов. Часть 2
В предыдущей статье я рассказывал про Big-O нотацию, и обещал привести примеры. Как обычно, простыми словами о сложных вещах. Напомним правило, что простые решения можно оценивать по количеству вложенных циклов.
O(1) - это одна операция для всех входных данных. Например, получить элемент массива по индексу. Это алгоритм с константным (постоянным) временем выполнения. То есть, какой бы ни был большой массив на входе, мы получим необходимый нам элемент из его состава простым запросом по индексу, в один подход, за одну операцию.
O(n) - это линейный алгоритм, итерации и время порядка n. Например, нам нужно получить сумму элементов массива, то есть перебрать все элементы. Будем перебирать один за другим и получим некоторое количество операций, а можем и не перебирать, а оптимизировать этот алгоритм и найти сумму всех элементов массива по формуле S=n(n+1)/2, где n-последний элемент массива, если он нам известен. Вот так вдруг из этого примера мы узнали про оптимизацию алгоритмов и привели алгоритм сложности O(n) к сложности O(1), то есть значительно его упростили.
O(n^2) - это алгоритмы с вложенным циклом, то есть n это количество циклов, в каждом цикле есть еще по одному циклу, значит будет n^2 циклов всего. Пример - двумерный массив, в котором каждый элемент массива имеет два индекса [x][y]array.
В следующей статье я продолжу эту тему.
Спасибо за то, что дочитали. Я буду очень рад если эта информация будет вам полезна. Подписывайтеь на мой канал. До встречи!