相关文章链接：

相关文章链接 第2节 数据结构

1.算法分析

算法分析分三个种类：

1. 最坏情况（Worst Case）：任意输入规模的最大运行时间。（Usually）

2. 平均情况（Average Case）：任意输入规模的期待运行时间。（Sometimes）

3. 最佳情况（Best Case）：通常最佳情况不会出现。（Bogus）

实际中，我们会按照最坏情况考量算法，也就是算法运行最长时间。一个算法的最坏情况运行时间是在任何输入下运行时间的一个上界（Upper Bound）。

2.算法复杂度

算法复杂度分为时间复杂度和空间复杂度

1. 时间复杂度是度量完成一个算法所需要的时间。

2. 空间复杂度是度量完成一个算法所需要占用的存储空间。

   时间和空间都是计算机资源的重要体现，而算法的复杂性就是体现在运行该算法时的计算机所需的资源多少。

2.1 O(1)、O(n)、O(logn)、O(nlogn)等

首先，我们了解一下渐近记号（Asymptotic Notation）通常有 O、 Θ 和 Ω 记号法。

1. Θ 记号渐进地给出了一个函数的上界和下界

2. 当只有渐近上界时使用 O 记号

3. 当只有渐近下界时使用 Ω 记号。

借助百度上的一张图来表示算法的时间复杂度的增长与处理数据多少的增长的关系。

时间复杂度的优劣

O(1)<O(logn)<O(n)<O(nlogn)<O(n²)<O(n³)<O(2ⁿ)<O(n!)<O(nⁿ)

常见的数量级大小：越小表示算法的执行时间频度越短，则越优。

2.2 例子

2.2.1 常量复杂度 O(1)

无论输入数据增大多少倍，耗时/耗空间都不变。

哈希算法就是典型的O(1)时间复杂度。

index = a;

a = b;

b = index;

2.2.2 线性复杂度 O(n)

数据量增大几倍，耗时也增大几倍。

package testAlgorithmicComplexity;

/**
 * 线性复杂度
 */
public class TestLinear {
    public static void main(String[] args) {
        int n = 10;
        int target = n;
        for (int i = 1; i < n+1; i++){
            if(target == i){
                System.out.println("第" + i + "次查找成功，值为：" + i);
                break;
            }
        }
    }
}

2.2.3 平方复杂度 O(n²)

数据量增大n倍时，耗时增大n的平方倍。

冒泡排序，就是典型的O(n²)的算法。

package testAlgorithmicComplexity;

import java.util.Arrays;

/**
 * 平方复杂度
 */
public class TestSquare {

    public static void main(String[] args) {
        int[] arr = new int[]{3, 5, 7, 9, 6, 2};
        for (int i = 0; i < arr.length; i++){
            for (int j = i; j < arr.length; j++){
                if(arr[j] < arr[i]){
                    int temp = arr[j];
                    arr[j] = arr[i];
                    arr[i] = temp;
                }
            }
        }
        System.out.println(Arrays.toString(arr));
    }
}

2.2.4 对数复杂度 O(logn)

当数据增大n倍时，耗时增大logn倍。

二分查找就是O(logn)的算法。

package testAlgorithmicComplexity;

/**
 * 对数复杂度
 */
public class TestLogarithm {

    public static void main(String[] args) throws Exception{
        int target = 195;
        int start = 1;
        int end = 256;
        int mid = (int) Math.ceil((double) (start + end - 1) / 2);
        double logarithm =  Math.log(start + end - 1) / Math.log(2);

        if(target < start || target > end){
            throw new Exception("目标值不在起始与截止范围内!");
        }
        int type;
        for(int i = 0; i < (int) logarithm; i++){
            type = doBinarySearch(mid, target);
            if(type == 0) {
                System.out.println("第" + (i+1) + "次查找成功，值为：" + mid);
                break;
            } else if(type == -1) {
                end = mid;
                mid = (int) Math.ceil((double) (start + mid - 1) / 2);
                continue;
            } else if(type == 1) {
                start = mid;
                mid = (int) Math.ceil((double) (end + mid - 1) / 2);
                continue;
            }
        }

    }

    /**
     * 比较中间数mid和目标值（-1：小于，0：等于，1：大于）
     * @param mid
     * @param value
     * @return
     */
    private static int doBinarySearch(int mid, int value){
        int result = 0;

        if(value < mid){
            result = -1;
        } else if(value > mid){
            result = 1;
        }

        return result;
    }
}