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

Материал из DISCOPAL
Перейти к: навигация, поиск
(не показаны 3 промежуточные версии этого же участника)
Строка 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>
 +
 
 +
[[Категория:Решенные задачи]]

Версия 12:10, 4 октября 2020