复杂度分析

究竟什么是大O？

是用时间复杂度来描述算法的性能，器关键是运行的算法的数据规模。

如果n是数据规模，O(f(n))表示运行算法所需要执行的指令数，和f(n)成正比

算法? ? ? ? ? ? ?	所需执行的指令数
二分查找法O(logn)	a*logn
寻找数组中的最大/最小值O（n）	b*n
归并排序算法O(nlogn)	c*nlogn
选择排序法O(n^2)	d*n^2

a,b,c,d为常数。随着处理数据的规模的增大，算法效率的改变与常数的关系是不大的。而是与后面的项关系巨大。因此，我们常常省略掉前面的常数。

现在举两个例子：

算法A：O(n)? 所需执行指令数:1000*n

算法B:O(n^2) 所需执行指令数：10*n^2

这里的常数是1000 和 10 随着数据规模的增大，n变大我们算法的效率也会发生改变，在n变大时，B的效率将会不如A。由此就可以得出结论，当n突破一个点的时候，时间复杂度低的算法一定比时间复杂度高的算法更高效。n越大效果越明显。

?严格来说，O(f(n))表示算法执行的上界。一般情况下，O来表示算法执行的最低上界。以此为基础，如果我们设计的算法有两部分，我们的算法以量级最高的算法为主导。

eg : O(nlogn + n) = O(nlogn)

现在来看一道题，要注意一下数据的规模应该如何取。

有一个字符串数组，将数组中的每一个字符串按照字母序排序;之后再将整个字符串数组按照字典序排序。整个操作的时间复杂度?

这里我们不能想当然的认为只用nlogn就能解决了而是应当考虑每个数组的长度与整个字符串数组有多少项两个条件，因为我们要求的是上界，那我们就夹着最长的字符串长度是s,一共有n项，就能解决这个问题，前后两部的算法分别是

O(n*slog(s))+O(s*nlog(n)).
?

数据规模

对于数据规模我们应当有一个大概的理解

如果要在1s内解决问题，O(n^2)的算法可以处理大约10^4级别的数据，O（n）的算法可以处理大约10^8级别的数据，O（nlogn）的算法可以处理大约10^7级别的数据

空间复杂度

通常来说，我们开了多大的辅助空间，我们就说我们用了多大的空间复杂度。、

eg：开了一个长度为n的辅助用的数组，空间复杂度就是O(n)级别

? ? ? ? 开了一个长度为n的辅助用的二维数组，空间复杂度就是O(n^2)级别

? ? ? ? ?开了一个常数空间，空间复杂度就是O(1)级别

?递归的调用是有空间代价的，一般来说递归的深度是多少，递归的空间复杂度就是多少。

简单的复杂度分析

O(1)

 void O_1( int a, int  b){
        int temp = a;
        a = b;
        a = temp;
    }

O（n）

 int sum (int n){
        int m = 0;
        for(int i = 0;i <= n;i++){
            m = m+i;
        }
        return m;
    }

O(n^2)

 void select (int arr[],int n){
        for(int i= 0; i < n; i++){
            int min = i;
            for(int j = i+1; j< n;j++){
                if(arr[j] < arr[min]){
                    min = j;
                }
            }
        }
    }

O(logn)

二分查找

 int sert (int arr[],int n,int target){
        int l = 0,r = n-1;
        while( l <= r){
            int mid = l + (r - l)/2;
            if(arr[mid] == target)return mid;
            if(arr[mid] > target)r = mid - 1;
            else l = mid +1;
        }
        return -1;
    }