Время Сложность - Big O

Question

Я пытаюсь решить следующие алгоритмы времени сложности:

s = 0; 
i = 1; 
while (s < n) { 
    s = s + i; 
    i = i + 1; 
} 

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

Я знаю, что он будет прокручивать цикл while 3 раза за n=5 и 10 раз за n=50, но как вы можете определить большое о этом?

Answer 1

Сроки: O(Sqrt(2n)).

Давайте предположим, что s=s+i и i=i+1 занять одну единицу времени, поэтому вопрос: учитывая n, что число i (т.е. количество while петель)?

Давайте посмотрим на значение с для каждой итерации:

iteration value of s 
1   s+1 
2   s+1+2 
3   s+1+2+3 
4   s+1+2+3+4 

Итак, ясно, после i итераций, значение s является суммой 1..i, что я * (я + 1)/2.

С s<=n, затем i*(i+1)/2<=n и поэтому i~Sqrt(2n).

EDIT

Простой C# код, чтобы увидеть выше:

int iterate(int n) 
{ 
    int s = 0; 
    int i = 1; 
    while (s < n) 
    { 
     s = s + i; 
     i = i + 1; 
     Console.WriteLine("s: {0}, i: {1} (Sqrt(2s): {2})",s,i,Math.Ceiling(Math.Sqrt(2*s))); 
    } 
    return i; 
} 

void Main() 
{ 
    iterate(1000); 
} 

производит следующую таблицу (что число i соответствует нашим Sqrt(2s)):

s: 1, i: 2 (Sqrt(2s): 2) 
s: 3, i: 3 (Sqrt(2s): 3) 
s: 6, i: 4 (Sqrt(2s): 4) 
s: 10, i: 5 (Sqrt(2s): 5) 
s: 15, i: 6 (Sqrt(2s): 6) 
s: 21, i: 7 (Sqrt(2s): 7) 
s: 28, i: 8 (Sqrt(2s): 8) 
s: 36, i: 9 (Sqrt(2s): 9) 
s: 45, i: 10 (Sqrt(2s): 10) 
s: 55, i: 11 (Sqrt(2s): 11) 
s: 66, i: 12 (Sqrt(2s): 12) 
s: 78, i: 13 (Sqrt(2s): 13) 
s: 91, i: 14 (Sqrt(2s): 14) 
s: 105, i: 15 (Sqrt(2s): 15) 
s: 120, i: 16 (Sqrt(2s): 16) 
s: 136, i: 17 (Sqrt(2s): 17) 
s: 153, i: 18 (Sqrt(2s): 18) 
s: 171, i: 19 (Sqrt(2s): 19) 
s: 190, i: 20 (Sqrt(2s): 20) 
s: 210, i: 21 (Sqrt(2s): 21) 
s: 231, i: 22 (Sqrt(2s): 22) 
s: 253, i: 23 (Sqrt(2s): 23) 
s: 276, i: 24 (Sqrt(2s): 24) 
s: 300, i: 25 (Sqrt(2s): 25) 
s: 325, i: 26 (Sqrt(2s): 26) 
s: 351, i: 27 (Sqrt(2s): 27) 
s: 378, i: 28 (Sqrt(2s): 28) 
s: 406, i: 29 (Sqrt(2s): 29) 
s: 435, i: 30 (Sqrt(2s): 30) 
s: 465, i: 31 (Sqrt(2s): 31) 
s: 496, i: 32 (Sqrt(2s): 32) 
s: 528, i: 33 (Sqrt(2s): 33) 
s: 561, i: 34 (Sqrt(2s): 34) 
s: 595, i: 35 (Sqrt(2s): 35) 
s: 630, i: 36 (Sqrt(2s): 36) 
s: 666, i: 37 (Sqrt(2s): 37) 
s: 703, i: 38 (Sqrt(2s): 38) 
s: 741, i: 39 (Sqrt(2s): 39) 
s: 780, i: 40 (Sqrt(2s): 40) 
s: 820, i: 41 (Sqrt(2s): 41) 
s: 861, i: 42 (Sqrt(2s): 42) 
s: 903, i: 43 (Sqrt(2s): 43) 
s: 946, i: 44 (Sqrt(2s): 44) 
s: 990, i: 45 (Sqrt(2s): 45) 
s: 1035, i: 46 (Sqrt(2s): 46)