Изменение сложности от O (N) к O (1)

Question

Для следующего кода:

s = 0 ; 
for(i=m ; i<=(2*n-1) ; i+=m) { 
     if(i<=n+1){ 
     s+=(i-1)/2 ; 
     } 
     else{ 
     s+=(2*n-i+1)/2 ; 
     }  
} 

Я хочу изменить сложность кода из O(n) в O(1). Поэтому я хотел исключить цикл for. Но так как сумма s хранит такие значения, как (i-1)/2 или (2*n-i+1)/2, поэтому устранение цикла включает утомительный подсчет значения пола каждого (i-1)/2 или (2*n-i+1)/2. Мне стало очень трудно это сделать, поскольку я мог бы получить неправильную формулу в суммах этажей. Могу ли вы, пожалуйста, помогите мне в изменении сложности от O(n) до O(1). Или, пожалуйста, помогите мне с этими суммами. Есть ли другой способ уменьшить сложность? Если да ... то как?

Answer 1

Как сказал дон Роби, существует обычное старое арифметическое решение вашей проблемы. Позвольте мне показать вам, как это сделать для первых значений i.

* EDIT 2: КОД ДЛЯ НИЖНЕЙ ЧАСТИ *

for(int i=m ; i<= n+1 ; i+=m)//old computation 
      s+=(i-1)/2 ; 


    int a = (n+1)/m; // maximum value of i 
    int b = (a*(a+1))/2; // 
    int v = 0; 
    int p; 
    if(m % 2 == 0){ 
     p = m/2; 
     v = b*p-a; // this term is always here 
    } 
    else{ 
     p = (m - 1)/2; 
     int sum1 = ((a/2)*(a/2 +1))/2; 
     int sum2 = (((a-1)/2)*((a-1)/2 +1))/2; 

     v = b*p -a ;// this term is always here 
     v+= sum1 + a/2; //sum(1 <= j <= a)(j-1), j pair 
     v+= sum2; //sum(1 <= j <= a)(j-1), j impair 
    } 
    System.out.println(" Are both result equals ? "+ (s == v)); 

Как придумать с ним? Я принимаю

for(i=m ; i<= n+1 ; i+=m) 
     s+=(i-1)/2 ; 

я внести изменения

for(j=1 ; j*m <= n-1 ; j++) 
    s+=(j*m-1)/2 ; 

Я задаю a=Math.floor(n+1/m). Существует 3 случая:

1. m является парой, затем внутренняя часть петли s+= p*j.Результат

   b(a*(a+1))/2 -a 
   

2. м это ухудшает и итератор J является парой

3. м это ухудшает и итератор J является ухудшать Когда м ухудшать, вы можете написать m = 2p + 1 и внутренняя часть петли становится

   s+= p*j + (j-1)/2 
   

p*j таким же, как и раньше, теперь вы должны разорвать разделение, полагая J всегда пара или j всегда ухудшают и суммируют оба значения.

Следующая петля вам нужно вычислить это

for(int i=a+1 ; i<= (2*n-1) ; i+=m)// a is (n+1)/m 
    s+=(2*n-i+1)/2; 

, который так же, как

for(int i=1 ; i<= (2*n-1)-a ; i+=m) 
    s+= (2n-a)/2 - (i-1)/2; 

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

Answer 2

Моим подходом к этому было бы сначала написать характеристические тесты, подтверждающие значения, полученные для разных значений m и n, а затем начать рефакторинг.

Ваш основной цикл имеет изменение логики, основанное на получении на полпути (выбор if(i<=n+1)), поэтому я сначала разделил его на две петли, основываясь на этом.

Тогда у вас есть в каждой из получающихся циклов, вычисление, которое зависит главным образом от того, является ли i четным или нечетным. Разделите каждый на 2 больше циклов, разделяющих их, и вычисления пола могут быть проще понять. Кроме того, вы можете увидеть шаблон повторяющихся значений, который упростит эти циклы другим способом.

Каждая из полученных циклов, скорее всего, будет похожа на сумму арифметической прогрессии, поэтому вы, скорее всего, обнаружите, что их можно заменить закрытыми вычислениями форм, не требующими вообще циклов.

Пока вы идете по этому пути, вы также можете реорганизовать, чтобы извлечь части вычисления в функции. Напишите характеристические тесты для них при их извлечении.

Продолжайте выполнять все ваши тесты по мере продолжения, и вы, вероятно, сможете уменьшить это до суммы простых вычислений, которые затем могут быть уменьшены в результате простой старой арифметики.