第2章算法分析

最大子序列和问题的求解

算法1：时间复杂度为O(N^3)

 1    public static int maxSubSum1(int [] a)
 2    {
 3        int maxSum = 0;
 4        
 5        for (int i = 0; i < a.length; i++)
 6            for (int j = i; j < a.length; j++)
 7            {
 8                int thisSum = 0;
 9                
10                for (int k = i; k < j; k++)
11                    thisSum += a[k];
12                
13                if (thisSum > maxSum)
14                    maxSum = thisSum;
15            }
16        
17        return maxSum; 
18    }

算法2：时间复杂度为O(n^2)

 1     public static int maxSubSum2(int [] a)
 2     {
 3         int maxSum = 0;
 4         
 5         for (int i = 0; i < a.length; i++)
 6         {
 7             int thisSum = 0;
 8             
 9             for (int j = i; j < a.length; j++)
10             {
11                 thisSum += a[j];
12                 
13                 if (thisSum > maxSum)
14                     maxSum = thisSum;
15             }
16         }
17         
18         return maxSum;
19     }

算法3：时间复杂度O(N logN)

 1    public static int maxSubRec(int [] a, int left, int right)
 2    {
 3        if(left == right)
 4            if (a[left] > 0)
 5                return a[left];
 6            else
 7                return 0;
 8 
 9        int center = (left + right) / 2;
10        int maxLeftSum = maxSubRec(a, left, center);
11        int maxRightSum = maxSubRec(a, center, right);
12 
13        int maxLeftBorderSum = 0, leftBorderSum = 0;
14        for (int i = left; i < center; i++)
15        {
16            leftBorderSum += a[i];
17            if (leftBorderSum > maxLeftBorderSum)
18                maxLeftBorderSum = leftBorderSum;
19        }
20 
21        int maxRighrBorderSum = 0, rightBorderSum = 0;
22        for (int i = center; i < right; i++)
23        {
24            rightBorderSum += a[i];
25            if (rightBorderSum > maxRighrBorderSum)
26                maxRighrBorderSum = rightBorderSum;
27        }
28 
29        return max3(maxLeftSum, maxRightSum, maxLeftBorderSum + maxRighrBorderSum);
30    }
31 
32    public static int max3(int a, int b, int c)
33    {
34        int max = (a > b) ? a : b;
35        return max = (max > c) ? max : c;
36    }
37 
38    public static int maxSubSum3(int [] a)
39    {
40         return maxSubRec(a, 0, a.length - 1);
41    }

算法4：时间复杂度O(N)

 1    public static int maxSubSum4(int [] a)
 2    {
 3        int maxSum = 0, thisSum = 0;
 4        
 5        for (int i = 0; i < a.length; i++)
 6        {
 7            thisSum += a[i];
 8            
 9            if (thisSum > maxSum)
10                maxSum = thisSum;
11            else if (thisSum < 0)
12                thisSum = 0;
13        }
14        
15        return maxSum;
16    }

折半查找 时间复杂度O(N)

 1    public static <AnyType extends Comparable<? super AnyType>>
 2    int binarySearch(AnyType[] a, AnyType x)
 3    {
 4        int low = 0, high = a.length - 1;
 5 
 6        while (low <= high)
 7        {
 8            int mid = (low + high) / 2;
 9 
10            if (a[mid].compareTo(x) < 0)
11                low = mid + 1;
12            else if (a[mid].compareTo(x) > 0)
13                high = mid - 1;
14            else
15                return mid;
16        }
17 
18        return -1;
19    }

欧几里得算法 计算最大公因数(log N)

 1    public static long gcd(long m, long n)
 2    {
 3        while (n != 0)
 4        {
 5            long rem = m % n;
 6            m = n;
 7            n = rem;
 8        }
 9 
10        return m;
11    }

高效率的幂运算 (logN)

 1    public static long pow(long x, int n)
 2    {
 3        if (n == 0)
 4            return 1;
 5        if (n == 1)
 6            return n;
 7        if (isEven(x))
 8            return pow( x * x, n / 2);
 9        else
10            return pow(x * x, n / 2) * x;
11    }
12 
13    public static boolean isEven(long x)
14    {
15        if ((x &1) == 0)
16            return true;
17        else
18            return false;
19    }

第2章 算法分析

第2章算法分析