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

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

Версия 08:11, 7 октября 2014

Преобразуем n к такому виду: Получается аналог поставленной задачи . Единственным отличием будет то, что необходимо будет запоминать значение для . Таким образом мы получили указанную оуенку.

Источник — «https://discopal.ispras.ru/index.php?title=Несложно_о_сложности._Примеры_алгоритмов/Задачи/ex-fast-power&oldid=3127»