算法分析

由最长子序和说起。。。
给定一组数据求其连续一组数据的和的最大值；
如：-2，11，-4，13，-5，-2；

 // 时间复杂度O（n）,，采用动态规划法
   public static int maxArraySum(int[] nums)
    {
        long start= new Date().getTime();
        int i;
        int maxsum=0,current=0;
        for(i=0;i<nums.length;i++){
            maxsum=Math.max(maxsum,current+nums[i]);
            if(current+nums[i]<0){
                current=0;
            }
            else {
                current=current+nums[i];
            }
            System.out.println(maxsum+" "+current);
        }
       long end=new Date().getTime();
        System.out.println((end-start)/1000.0);
        return maxsum;
    }
n

   // 采用镶嵌循环，时间复杂度为O（n*n）
    public static int maxArraySum2(int[] nums)
    {
        long start= new Date().getTime();
        int maxsum=0;
        for(int i=0;i<nums.length;i++){
            int sum=0;
            for(int j=i;j<nums.length;j++){
               sum=sum+nums[j];
               if(sum>maxsum){
                   maxsum=sum;
               }
            }
        }
       long end=new Date().getTime();
        System.out.println((end-start)/1000.0);
        return maxsum;
    }

// 100000 测试数据数目
    Random random=new Random();
        int[] nums=new int[1000000];
      for(int i=0;i<nums.length;i++){
          nums[i]=random.nextInt(10)*100-500;
      }
     System.out.println(Main.maxArraySum2(nums));
     System.out.println(Main.maxArraySum(nums));


---运行时间
1、3.752
   7000
2、0.004
   7000

因此算法重要性不言而喻了；

折半查找

public static int finditem(int[] nums,int item){
        int start=0,last=nums.length-1;
        while (start<=last){
            int mid=(last+start)/2;
            System.out.println(mid);
            if(item>nums[mid]){
                start=mid+1;
            }
            else if(item<nums[mid]){
                last=mid-1;
            }
            else
                return mid;
        }
        return -1;
    }