Я не умею определять время и сложность памяти и был бы признателен, если бы кто-нибудь помог мне.
У меня есть алгоритм, здесь, и я не уверен, каковы будут его сложность времени и памяти.
Function sample(k)
IF k < 2
Return 0
Return 1 + sample(k/2)
Какова его сложность времени и памяти и почему?
Спасибо
Определение сложности времени и памяти сводится к подсчету того, сколько из этих двух ресурсов используется при выполнении алгоритма, и просмотру того, как эти количества изменяются в зависимости от размера входных данных (в данном случае k ) изменения.
Время будет определяться тем, сколько раз оценивается каждая из инструкций, а пространство будет определяться тем, насколько большими должны быть задействованные структуры данных для вычисления решения.
В этом конкретном сценарии вы смотрите на рекурсивный алгоритм, поэтому в основном это включает подсчет 1) количества сделанных рекурсивных вызовов и 2) объема работы, выполняемого для каждого из этих вызовов.
Поскольку ввод удваивается при каждом вызове, последовательность вызовов будет выглядеть примерно так:
sample(k) )
sample(k/2) )
sample(k/4) )
... ) - n = number of calls
sample(4) )
sample(2) )
sample(1) )
Уполовинивание каждого рекурсивного вызова таким образом приведет к логарифмическому количеству вызовов.
n = log(k)
При каждом вызове мы сохраняем постоянное количество переменных в стеке вызовов и выполняем постоянный объем работы (операций). Это связано с тем, что количество переменных и количество сравнений/сложений/делений в каждом вызове не увеличивается с увеличением k.
Общая временная сложность — это количество вызовов, умноженное на объем работы, выполненной в каждом вызове, таким образом
time complexity = A*log(k) + B
Для некоторых констант A и B, которые отражают фактические затраты времени на выполнение рекурсивного вызова и выполнение сравнений/делений соответственно. Сходным образом:
space complexity = C*log(k) + D
Для констант C и D подходят подходящие для памяти затраты на рекурсию и хранение переменных соответственно.
Теперь в такого рода анализе мы в основном заботимся об асимптотической сложности, то есть нас действительно не заботят константы, потому что они отражают детали машины, на которой работает алгоритм, и мы действительно хотим знать форму кривой ( по мере увеличения k). Если вы будете следовать правилам написания сложности с использованием нотации Big-Oh, вы получите результат:
space complexity = time complexity = O(log(k))
Как я уже говорил, сложность памяти определяется тем, насколько большими должны быть структуры данных для вычисления решения, поэтому вы можете спросить: в этой функции не используются структуры данных, так куда же девается память log(k)?
Короткий ответ: вам нужно сохранить log(k) различных значений параметра k, по одному для каждого рекурсивного вызова.
Подробный ответ: существует неявная структура данных, используемая здесь механизмом вызова функций (который мы используем с помощью рекурсии), и ее имя - стек вызовов. Каждый раз, когда вызывается sample(k), создается новый кадр стека, и в стек помещается ряд значений: локальное значение параметра k, адрес возврата и другие вещи, зависящие от реализации. Таким образом, каждый рекурсивный вызов формирует «слой» в стеке, где хранится его локальная информация. В итоге картина выглядит примерно так:
----------- < top of stack
| k = 1 |
| ... | < stack frame for sample(1)
|---------|
| k = 2 |
| ... | < stack frame for sample(2)
|---------|
...
|---------|
| k = p/2 |
| ... | < stack frame for sample(p/2)
|---------|
| k = p |
| ... | < stack frame for sample(p)
|---------|
| | < stack frame for main() or whatever
initially called sample(p)
(we don't count this one)
(Я отличил здесь начальное значение параметра p от значения k при каждом рекурсивном вызове, чтобы избежать путаницы, надеюсь)
Главное отметить, что поскольку рекурсивных вызовов n = log(k), таких кадров стека n. Каждый кадр стека имеет постоянный размер, поэтому сложность пространства равна O(log(k)).
Вы действительно смотрите на log_2 (k), логарифм с основанием 2. Чтобы изменить основание, вы должны умножить на константу. И так как мы все равно умножаем на константы, O(log(n)), O(ln(n)) и O(log_2(n)) одинаковы.
Так почему же вышеупомянутый метод имеет логарифмическую сложность с основанием 2? Вы делите k пополам при каждом звонке. Если вы идете назад, вы умножаете на 2 при каждом вызове. Умножение на 2 равно 2 ^ n, а log_2(n) в точности противоположно этому.
Может быть, это поможет, если вы нарисуете двоичное дерево: дерево с n узлами имеет высоту log_2 (n), дерево с высотой n имеет 2 ^ n узлов.
