算法复杂度分析基于以下四条定义:
若使用比较简单(不甚准确)的表达:
时间估算中,认为每个操作花费时间为1,跳转,判断等所消耗时间可以忽略,例如
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)
考虑最简单直接的解法,计算出以某个数开头的所有子序列和,取出最大的值
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(结尾位置)都要重新计算全部子序列和。其实前面的和是被重复计算了,计算下一个子序列和时只需要加上结尾的值就可以了。
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
分治法解决这个问题的方法是:找出左侧一半的最大子串,找出右侧一半的最大子串,找出跨越左右分界的最大子串(左侧终点确定,右侧起点确定),比较得最大值。
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
该算法原理还未理解透彻,正在研究中
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