Ты должен знать
- алгоритм
- кратчайший путь по алгоритму
- самый длинный путь по алгоритму
- как длина пути или количество итераций меняются в зависимости от количества обрабатываемых элементов данных
- как выглядит "средний" набор данных.
Временную сложность наилучшего случая можно рассчитать, учитывая, что происходит со временем выполнения или количеством итераций, когда вы увеличиваете набор данных на 1 элемент, на 2 элемента, в 2 раза, в 3 раза. Если время выполнения увеличение линейно зависит от количества элементов данных, мы говорим, что временная сложность равна O (N), то есть порядка N - количества элементов данных. Если время выполнения изменяется как квадрат количества элементов данных, то мы говорим, что временная сложность равна O (N
2 ). Временная сложность может быть другого порядка, экспоненциальной или иметь другое отношение к количеству элементов данных, например, O (N
3/2 ).
Такая же оценка временной сложности может быть сделана для худшего и среднего случаев.