При кодировании алгоритма многие программисты просто хотят, чтобы алгоритм работал, забывая, что хороший алгоритм не просто работает, он работает оптимально. Чтобы измерить, насколько оптимален алгоритм, существует нотация Big O, но что такое нотация Big O? Обозначение «большое О» является наиболее популярным способом измерения времени, необходимого для выполнения алгоритма в худшем случае, например, когда вы ищете один элемент в списке из N элементов, а искомый элемент находится в последнем. положение списка.
Есть много различных сложностей (время выполнения), но наиболее распространенными из них являются
- O(1)
- О(логN)
- O(N)
- O(NlogN)
- O(N²)
O(1) является самым быстрым и представляет собой время, необходимое компьютеру для выполнения математической операции, такой как 2+2 или 105641019 + 999.
Самое медленное время выполнения в списке — N², это когда у вас есть два вложенных цикла с одинаковыми границами.
Примеры времени компиляции:
- O(1):
- Математические операции
- Доступ к позиции в массиве
- O(logN): бинарный поиск
- O(N):
- Одна петля
- ДФС
- О(NlogN):
- Алгоритм Крускала
- Время построения дерева сегментов
- O(N²):
- Два вложенных цикла
На сегодня все, следующие посты будут про алгоритмы соревновательного программирования.
