时间复杂度

衡量代码的好坏，包括两个非常重要的指标：

• 运行时间
• 占用空间

由于运行环境和输入规模的影响，代码的绝对执行时间是无法估计的，但是我们却可以预估代码的基本执行次数。我可以通俗的理解为：通过执行次数可以大概推算这个时间复杂度。

示例：

• 一个有序排列好的数组

  int[] arry = {-5,-1,0,5,9,11,13,15,22,35,46},输入一个x，int x = 31

  在数组中找出和为 x 的两个数，例如： 9 +22 = 31。要求时间复杂度为O(n).

好，当我们看到这个问题的时候，我们认为这很容易嘛(先不考虑时间复杂度)，于是写了如下代码：

第一种写法：

int[] array = {-5,-1,0,5,9,11,13,15,22,35,46};
 int sum = 31;

public void getIndex(int[] array,int sum){
        //sum 在数据中找出和为sum的两个数
        int x = 0;
        int y = 0;
        for(int i=0;i<array.length;i++){
            for(int j=i+1;j<array.length;j++){
                //判断是否相加=sum
                if(array[i] + array[j] == sum){
                    x = i;
                    y = j;
                    break;
                }
            }
        }
        System.out.println("第一个数的为："+array[x]);
        System.out.println("第二个数的为："+array[y]);
    }

根据我们上面对时间复杂度的了解，我们知道改算法的时间复杂度是 O(n^2)， 是最低的一种，可以说，那么我们如何把时间复杂度设置为O(n) ,线性复杂度，其实就是需要一遍for 循环；

第二种算法：

int[] array = {-5,-1,0,5,9,11,13,15,22,35,46};
int sum = 31;

public  void getSimpleIndex(int[] array,int target){
        int x = 0;
        int y = 0;
        HashMap<Integer, Integer> hm = new HashMap<Integer, Integer>();
        for (int i = 0; i < array.length; i++) {//第一次遍历数组，将元素和下标以K-V方式存入hm中
            hm.put(array[i], i);//key 为数组里面的值，value是下标
        }
        for(int i=0;i<array.length;i++) {//第二次遍历数组，查找是否有和为target的元素对
            if (hm.containsKey(target - array[i]) && (i != hm.get(target - array[i]))) {
                //保证两个元素不是同一个，否则如果target恰好是某个元素的2倍时就不符合题意
                x = i;
                y = hm.get(target - array[i]);
                break;
            }
        }
        System.out.print(array[x]+" "+array[y]);
    }

这是一种典型以空间换时间的解法。

总结

常见的时间复杂度有如下：

• T(n) = O(n)
• T(n) = O(logn)
• T(n) = O(1)
• T(n) = O(n²)

这四种时间复杂度谁用时更长，更节省时间呢？

O(1) < O(logn) < O(n) < O(n²)