算法复杂度分析
算法复杂度基本定义
算法复杂度分析基于以下四条定义:
- 如果存在常数c与$n{0}$使$N \geq n{0} $时,有$T(N) \leq cf(N)$,则记 $T(N) = O(f(N))$
- 如果存在常数c与$n{0}$使$N \geq n{0} $时,有$T(N) \geq cf(N)$,则记 $T(N) = \Omega(f(N))$
- 当且仅当$T(N) = O(f(N))$且$T(N) = \Omega(f(N))$时,记$T(N) = \Theta(f(N))$
- 若$T(N) = O(f(N))$且$T(N) \neq \Theta(f(N))$时,记$T(N) = o(f(N))$
若使用比较简单(不甚准确)的表达:
- 当T(N)增长的比f(N)慢的时候,认为$T(N) = O(f(N))$
- 当T(N)增长的比f(N)快的时候,认为$T(N) = \Omega(f(N))$
- 当T(N)和f(N)一样快的时候,认为$T(N) = \Theta(f(N))$
算法复杂度分析运算
- 加法:T1(N)=O(f(x)),T2(N)=O(g(x)),则T1(N) + T2(N) = max{O(f(x)),O(g(x))}
- 乘法:同上假设,T1(N) T2(N) = O(f(x) g(x))
算法时间估算
时间估算中,认为每个操作花费时间为1,跳转,判断等所消耗时间可以忽略,例如
1 2 3 4 5 6
| for(i = 0;i < N;i++) { for(j = 0;j < N;j++) { a += i+ j; } b += i; }
|
分析以上算法,内循环一次耗时N,外循环一次耗时$N * (N + 1) = N^{2} + N$,时间估算中忽略常数项和低次项,该算法花费时间$O(N^{2})$,由以上可以得出一些结论:
- 顺序语句:时间估算为语句中耗时最多的一条
- 判断语句:时间估算为不超过所有分支运算时间之和(与选择最耗时的一个分支相同)
- 循环语句:时间估算为循环次数的乘积(包括嵌套循环)
最大子序列问题
问题
已知一个序列,要求求和最大的连续子序列的和。例如输入-2,11,-4,13,-5,-2,输出20(11-4+13)
求解
解法一:真.暴力求解
考虑最简单直接的解法,计算出以某个数开头的所有子序列和,取出最大的值
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
| 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 }
|
解法二:改进.暴力求解
考虑以上求和的部分,每改一个j(结尾位置)都要重新计算全部子序列和。其实前面的和是被重复计算了,计算下一个子序列和时只需要加上结尾的值就可以了。
1 2 3 4 5 6 7 8 9 10 11 12 13
| 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 }
|
解法三:分治法
分治法解决这个问题的方法是:找出左侧一半的最大子串,找出右侧一半的最大子串,找出跨越左右分界的最大子串(左侧终点确定,右侧起点确定),比较得最大值。
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
| func solution3(data []int) int { if len(data) == 1 { return data[0] } split_num := int(len(data) / 2) 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 } }
|
解法四:动态规划/贪心算法
该算法原理还未理解透彻,正在研究中
1 2 3 4 5 6 7 8 9 10 11 12
| 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 }
|