Блог

Я понимаю оба алгоритма, однако временная сложность кажется мне странной.

Если вы посмотрите на оба дерева, сгенерированные обоими алгоритмами, вы увидите, что они абсолютно одинаковы, мы продолжаем делить дерево на две половины, пока не дойдем до конца.

Так почему же один алгоритм имеет сложность 2^N, а другой-nlog(n) ?

O(2^log(n)) по существу то же самое, что и O(n). В своем вопросе вы упоминаете 2^n. Вы, вероятно, хотите исправить название этого вопроса. Я не уверен, что вы подразумеваете под деревом, сгенерированным рядом Фибоначчи. Дерево Фибоначчи имеет 4 указателя на узел, но я не думаю, что это то, о чем вы спрашиваете.

Наивный рекурсивный расчет Фибоначчи равен 2^n, потому что он дублирует вычисления, вычисляя F(n-1), который, в свою очередь, вычисляет F(n-2), а затем вычисляет F(n-2) во второй раз.

При размере массива, равном степени 2, на самом глубоком уровне рекурсии будет создано n экземпляров поддиапазонов размером 1. Затем на следующем самом глубоком уровне n/2 экземпляра объединения пар запусков размером 1 занимают O(n) общего времени. Следующий уровень-это n/4 экземпляров, объединяющих пары запусков размером 2, также отнимающих O(n) общего времени. Таким образом, общая временная сложность равна O(n log2(n)).