Algorithms Flashcards
- Что такое нотация большое О.
Нотация “большое О” — это способ описания того, как быстро растет что-то по мере увеличения входных данных. Например, если у вас есть алгоритм, который решает задачу, то “большое О” помогает понять, как долго будет работать этот алгоритм при увеличении объема данных.
Вот упрощенный пример:
1. Время работы алгоритма: Представьте, что у вас есть алгоритм, который нужно выполнить для разных размеров данных. Нотация “большое О” помогает сказать, насколько быстро будет увеличиваться время выполнения алгоритма по мере увеличения объема данных.
2. Пример с числами:
o Если время работы алгоритма описывается как O(n)O(n)O(n), это значит, что время выполнения алгоритма растет прямо пропорционально размеру данных. Если объем данных удваивается, время выполнения тоже удваивается.
o Если время работы алгоритма описывается как O(n2)O(n^2)O(n2), это значит, что время выполнения растет в квадрате от размера данных. Если объем данных увеличивается в 2 раза, время выполнения увеличивается в 4 раза (2^2).
По сути, “большое О” помогает нам понять, как быстро алгоритм станет медленнее или как быстро он потребляет ресурсы, когда данные становятся больше. Это полезно для оценки и сравнения алгоритмов, чтобы выбрать наиболее эффективный.
- Какова сложность добавления и получения элемента в Dictionary.
O(1) в обычном случае, O(n) в худшем
