111029_演算法的特性

The properties of  algorithm ?

1. Finiteness(有限性)

    terminates after a finite number of steps

2. Definiteness(明確性)

    rigorously and unambiguously specified

3. Input

    valid inputs are clearly specified

4. Output

    can be proved to produce the correct    

    output given a valid input

5. Effectiveness(有效性，可用紙筆計算)

    basic steps are sufficiently simple and basic

111015_演算法_螞蟻演算法

螞蟻演算法
當蟻群會在巢穴與食物間找到一條最短路徑。

參考：http://iridia.ulb.ac.be/~mdorigo/ACO/index.html

111025_演算法_雙迴圈的時間複雜度

(a)
for(a=1; a<N; a++)
    for(b=1; b<=N; b++)
        c++;
解:
∑_a=1^N-1∑_b=1^N 1 
= ∑_a=1^N-1．N
= N∑_a=1^N-1１  
= N(N-1) 
≈ N² 
∈ O(N²)


(b)
for(a=1; a<N; a++)
    b++;
解:
∑_a=1^N-1 1 = N-1 ≈ N ∈ O(N)


(c)
for(a=1; a<N; a++)
    for(b=a; b<7; b++)
        c++;
解:
∑_a=1^N-1∑_b=a ⁶ 1 
= ∑_a=1^N-1(6-a+1) 
= ∑_a=1^N-1(7-a)      
= 7∑_a=1^N-11 - ∑_a=1^N-1a   
= 7(N-1-1+1) - (1+N-1)(N-1)/2
= 7(N-1) - N(N-1)/2
≈ N²
∈ O(N²)