时间复杂度和最大子序列问题

 运行时间计算

法则1——for循环

一个for循环的运行时间最多是该for循环内部那些语句（包括测试）的运行时间乘以迭代的次数。

法则2——嵌套的for循环

从里向外分析这些循环，在一组嵌套循环内部的一条语句的运行时间为该语句的运行时间乘以该组所有的for循环的大小的乘积。

法则3——顺序语句

将各个语句的运行时间求和即可。

法则4——if/else语句

一个if/else语句的运行时间不会超过判断的运行时间再加上S1和S2中运行时间长者的总的运行时间。

下面通过四种算法来比较最大子序列问题的时间复杂度

<span style="font-size:24px;">package Algorithm;

public class Test1 {
// 方法一   穷举法
public static int GetMaxNum1(int a[]) {
int max = 0;
for (int i = 0; i < a.length; i++) {
for (int j = i; j < a.length; j++) {
int num = 0;
for (int k = i; k <= j; k++) {
num += a[k];
}
if (num > max) {
max = num;
}
}
}
return max;
}
   //方法二    省略一层循环
public static int GetMaxNum2(int a[]) {
int max = 0;
for (int i = 0; i < a.length; i++) {
int num = 0;
for (int j = i; j < a.length; j++) {
num += a[j];
if (num > max) {
max = num;
}
}
}
return max;
}
   //方法三    分治法利用递归
public static int GetMaxNum3(int a[], int left, int right) {
if (left == right) {
if (a[left] < 0)
return 0;
else
return a[left];
}
int center = (left + right) / 2;
int maxleft = GetMaxNum3(a, left, center);
int maxright = GetMaxNum3(a, center + 1, right);
int leftmax = 0, leftnum = 0;
for (int i = center; i >= left; i--) {
leftnum += a[i];
if (leftnum > leftmax) {
leftmax = leftnum;
}
}
int rightmax = 0, rightnum = 0;
for (int j = center + 1; j <= right; j++) {
rightnum += a[j];
if (rightnum > rightmax) {
rightmax = rightnum;
}
}

return getMax(maxleft, maxright, leftmax + rightmax);
}
//方法四   非常聪明简单的方法
public static int GetMaxNum4(int[] a){
int max = 0, num = 0;
for (int i = 0; i < a.length; i++) {
num += a[i];
if (num > max) {
max = num;
     }else if(num <0){
num=0;
}
}
return max;
}

public static int getMax(int maxleft, int maxright, int num) {
if (maxleft > maxright) {
if (maxleft > num)
return maxleft;
else
return num;
} else {
if (maxright > num)
return maxright;
else
return num;
}
}

public static void main(String[] args) {
int[] a = { 4, -3, 5, -2, -1, 2, 6, -2 };
System.out.println(GetMaxNum3(a,0,a.length-1));
System.out.println(GetMaxNum1(a));
System.out.println(GetMaxNum2(a));
System.out.println(GetMaxNum4(a));
}
}
</span>

第一种方法采用穷举法，将每一种情况列举出来一一比较，算法复杂度较高达到O(n3)

第三种方法采用分治法的思想，其思想就是把问题分成两个大致相等的子问题，然后递归地对它们求解。最后将两个子问题修补到一起并可能做些少量的附加工作，最后得到整个问题的解。

第四种方法效果最高，为O(n)