算法復(fù)雜度分析

算法復(fù)雜度基本定義

算法復(fù)雜度分析基于以下四條定義：

• 如果存在常數(shù)c與$n_{0}$使$N \geq n_{0} $時(shí)，有$T(N) \leq cf(N)$，則記 $T(N) = O(f(N))$
• 如果存在常數(shù)c與$n_{0}$使$N \geq n_{0} $時(shí)，有$T(N) \geq cf(N)$，則記 $T(N) = \Omega(f(N))$
• 當(dāng)且僅當(dāng)$T(N) = O(f(N))$且$T(N) = \Omega(f(N))$時(shí)，記$T(N) = \Theta(f(N))$
• 若$T(N) = O(f(N))$且$T(N) \neq \Theta(f(N))$時(shí)，記$T(N) = o(f(N))$

若使用比較簡(jiǎn)單（不甚準(zhǔn)確）的表達(dá)：

• 當(dāng)T(N)增長(zhǎng)的比f(wàn)(N)慢的時(shí)候，認(rèn)為$T(N) = O(f(N))$
• 當(dāng)T(N)增長(zhǎng)的比f(wàn)(N)快的時(shí)候，認(rèn)為$T(N) = \Omega(f(N))$
• 當(dāng)T(N)和f(N)一樣快的時(shí)候，認(rèn)為$T(N) = \Theta(f(N))$

算法復(fù)雜度分析運(yùn)算

• 加法：T1(N)=O(f(x))，T2(N)=O(g(x))，則T1(N) + T2(N) = max{O(f(x)),O(g(x))}
• 乘法：同上假設(shè)，T1(N)* T2(N) = O(f(x) * g(x))

算法時(shí)間估算

時(shí)間估算中，認(rèn)為每個(gè)操作花費(fèi)時(shí)間為1，跳轉(zhuǎn)，判斷等所消耗時(shí)間可以忽略，例如

for(i = 0;i < N;i++) {
  for(j = 0;j < N;j++) {
    a += i+ j;
  }  
  b += i;
}

分析以上算法，內(nèi)循環(huán)一次耗時(shí)N，外循環(huán)一次耗時(shí)$N * (N + 1) = N^{2} + N$，時(shí)間估算中忽略常數(shù)項(xiàng)和低次項(xiàng)，該算法花費(fèi)時(shí)間$O(N^{2})$，由以上可以得出一些結(jié)論：

• 順序語(yǔ)句：時(shí)間估算為語(yǔ)句中耗時(shí)最多的一條
• 判斷語(yǔ)句：時(shí)間估算為不超過(guò)所有分支運(yùn)算時(shí)間之和（與選擇最耗時(shí)的一個(gè)分支相同）
• 循環(huán)語(yǔ)句：時(shí)間估算為循環(huán)次數(shù)的乘積（包括嵌套循環(huán)）

最大子序列問(wèn)題

問(wèn)題

已知一個(gè)序列，要求求和最大的連續(xù)子序列的和。例如輸入-2，11，-4，13，-5，-2，輸出20（11-4+13）

求解

解法一：真.暴力求解

考慮最簡(jiǎn)單直接的解法，計(jì)算出以某個(gè)數(shù)開頭的所有子序列和，取出最大的值

func solution1(data []int, num int) int {
    max_sum, this_sum := 0, 0
    for i := 0; i < num; i++ {
        for j := i; j < num; j++ {
            this_sum = 0
            for k := i; k < j; k++ {
                this_sum += data[k]
            }
            if this_sum > max_sum {
                max_sum = this_sum
            }
        }
    }
    return max_sum
} //done: 1.1903458s

解法二：改進(jìn).暴力求解

考慮以上求和的部分，每改一個(gè)j（結(jié)尾位置）都要重新計(jì)算全部子序列和。其實(shí)前面的和是被重復(fù)計(jì)算了，計(jì)算下一個(gè)子序列和時(shí)只需要加上結(jié)尾的值就可以了。

func solution2(data []int) int {
    max_sum, this_sum, num := 0, 0, len(data)
    for i := 0; i < num; i++ {
        this_sum = 0
        for j := i; j < num; j++ {
            this_sum += data[j]
            if this_sum > max_sum {
                max_sum = this_sum
            }
        }
    }
    return max_sum
} // done: 1.115286s

解法三：分治法

分治法解決這個(gè)問(wèn)題的方法是：找出左側(cè)一半的最大子串，找出右側(cè)一半的最大子串，找出跨越左右分界的最大子串（左側(cè)終點(diǎn)確定，右側(cè)起點(diǎn)確定），比較得最大值。

func solution3(data []int) int {
    if len(data) == 1 {
        return data[0]
    }
    split_num := int(len(data) / 2)
    // fmt.Println(split_num)
    left_max := solution3(data[:split_num])
    right_max := solution3(data[split_num:])

    mid_left_max, mid_right_max := 0, 0
    mid_left, mid_right := 0, 0
    for i := split_num; i >= 0; i-- {
        mid_left += data[i]
        if mid_left > mid_left_max {
            mid_left_max = mid_left
        }
    }
    for i := split_num + 1; i < len(data); i++ {
        mid_right += data[i]
        if mid_right > mid_right_max {
            mid_right_max = mid_right
        }
    }
    mid_max := mid_left_max + mid_right_max
    if (mid_max > left_max) && (mid_max > right_max) {
        return mid_max
    } else if left_max > right_max {
        return left_max
    } else {
        return right_max
    }
} //done: 1.1223139s

解法四：動(dòng)態(tài)規(guī)劃/貪心算法

該算法原理還未理解透徹，正在研究中

func solution4(data []int) int {
    max_sum, this_sum, num := 0, 0, len(data)
    for i := 0; i < num; i++ {
        this_sum += data[i]
        if this_sum < 0 {
            this_sum = 0
        } else if this_sum > max_sum {
            max_sum = this_sum
        }
    }
    return max_sum
} //done: 1.1323284s