Блог пользователя So_Cold

Formula
Автор So_Cold, история, 8 лет назад, По-английски 
for i = 1 to n 
    ans+=pow(x,i)

can it calculated in less than o(n) ? thanks in advance

  • Проголосовать: нравится
  • +7
  • Проголосовать: не нравится

»
8 лет назад, # |
← Rev. 2   Проголосовать: нравится +2 Проголосовать: не нравится

link

Also you can do it preety easily in .

→ Ответить
»
8 лет назад, # |
← Rev. 3   Проголосовать: нравится 0 Проголосовать: не нравится

This is the sum of a geometric series so it can be calculated fast by divide and conqueror approach.

Let n = 2k then y = x1 + x2 + ... + xk, and then the sum is y + xk * y.

→ Ответить