Несложно о сложности. Примеры алгоритмов/Задачи/ex-fast-power — различия между версиями

Версия 00:13, 26 декабря 2014

@@ Строка 1: / Строка 1: @@
-Преобразуем n к такому виду:
+<latex>
-<math>n=2^{k-t}*(2^t+2^{t-1}+...+2+1)=2^{k-t}*((1-1*2^{t+1})/(1-2))=2^{k+1}-2^{k-t}</math>
+Более внимательно взглянув на алгоритм быстрого возведения в~степень, видно, что достаточно $2(\log_2 n +1)$ умножений.
-Получается аналог поставленной задачи <math>2^n</math>. Единственным отличием будет то, что необходимо будет запоминать значение для <math>2^{k-t}</math>. Таким образом мы получили указанную оуенку.
+На самом деле, как видно из изложенного, для чисел вида $n=2^k$  достаточно $k=\log {_2} n+1$ умножений.
+Можно ли получить такую же асимптотическую оценку $\sim \log {_2} n$ для чисел вида $n=2^k+2^{k-1}+2^{k-2}+\ldots+2^{k-t}$?
-[[Категория:На проверку]]
+Для произвольных чисел?
+</latex>
+[[Category:Решенные задачи]]