題目

計算1加到n的總和，例如: n為10，總和為1+2+3+4+5+6+7+8+9+10=55。

解法一

時間複雜度: O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
"""
透過數學累加方式進行計算總和

若n=10

計算方式:
0 + 1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 55
步驟1 => total + 1 => 0 + 1 = 1
步驟2 => total + 2 => 1 + 2 = 3
步驟3 => total + 3 => 3 + 3 = 6
步驟4 => total + 4 => 6 + 4 = 10
步驟5 => total + 5 => 10 + 5 = 15
步驟6 => total + 6 => 15 + 6 = 21
步驟7 => total + 7 => 21 + 7 = 28
步驟8 => total + 8 => 28 + 8 = 36
步驟9 => total + 9 => 36 + 9 = 45
步驟10 => total + 10 => 45 + 10 = 55
"""


def sum_1_to_n(n):
    total = 0
    for i in range(1, n + 1):
        total = total + i
        print(f'步驟{i} = total + {i} = {total} + {i} = {total + 1}')

    return total


print(f"總和: { sum_1_to_n(10) }")

解法二

時間複雜度: O(n)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
"""
透過遞迴方式進行計算總和

若n=10

計算方式:
1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 + 10 = 55

將問題拆解成小問題，找出遞迴的關係式
x=1時, r(1) => return 1
x=2時, r(2) => return r(1) + 2 =>  1 + 2 = 3
x=3時, r(3) => return r(2) + 3 =>  3 + 3 = 6
...
x=10時, r(10) => return r(9) + 10 =>  45 + 10 = 55

遞迴展開:
r(10){
  return r(9){
     return r(8){
        return r(7){
           return r(6){
              return r(5){
                 return r(4){
                    return r(3){
                       return r(2){
                          return r(1){
                             return 1
                          } + 2
                       } + 3
                    } + 4
                 } + 5
              } + 6
           } + 7
        } + 8
     } + 9
  } + 10
}
"""


def r(n):
    if n == 1:
        return 1

    return r(n - 1) + n


print(f"總和: { r(10) }")

Keyword

1
2
3
演算法, Algorithm, al-go-rithm
遞迴, Recursion, re-cur-sion
時間複雜度, Time complexity, time com-ple-xity