时光老头
数据结构和算法因何而生？其实它们的存在就是为了解决“快”和“省”两个问题。也就是如何让代码运行的效率更快！让代码的执行更节省存储空间！而时间复杂度和空间复杂度就是来衡量我们的代码是否快！是否省！掌握了这两种分析技能我们就能炼成火眼金睛！一眼瞄出“快”和“省”的代码！
时间复杂度
来咱们先看一段代码
1 int count(int n){
2 int sum = 0;
3 for(int i = 1; i <= n; i++){
4 sum = sum + i;
5 }
6 return sum;
7 }
虽然每行代码具体的执行时间是不一样的，但是我们就粗略的认为每一行代码执行的速度都为t，那这情况就是第二行t+第三行n*t+第四行n*t+第六行t。所以这段代码的总执行时间就是2t+2n*t。我们可以看到这段代码执行的总时间和每行代码执行的次数n成正比！
则可提取出一个公式T（n）=O（f(n)）。从我们的例子来看就是T（n）=O(2n+2)，而当n很大的时候，公式种的常量系数和低阶部分都不会影响整体的增长情况，所以可以忽略了，因此可以记为T（n）=O(n) 这就是我们的大0时间复杂度表示法了！
大O时间复杂度实际也叫渐进时间复杂度(asymptotic time complexity)，简称时间复杂度，它实际上表明的只是代码的执行时间随数据规模增长的变化趋势，而不是代码执行的具体时间。
咱再来看一段代码，我把每行的执行时间直接标注在代码后面
1 int count(int n){
2 int sum1 = 0; //t
3 int sum2 = 0; //t
4 int squareN = n*n; //t
5 for(int i = 1; i <= n; i++){ //n*t
6 sum1 = sum1 + i; //n*t
7 }
8 for(int i = 1; i <= squareN; i++){ //n²*t
9 sum2 = sum2 + i; //n²*t
10 }
11 return sum1+ sum2; //t
12 }
按照咱们上面说的提取出的大致总执行时间4t+2n*t+2n²*t =>t(2n+2n²+4)得到T(n) = O(2n+2n²+4)。
又因为可以忽略常量系数和低阶部分，所以最终记为T(n) = O(n²)。
所以我们只需要关注循环次数最多的那一行代码！它的执行次数就代表我们的时间复杂度
其实虽然代码有五花八门，但是常见的时间复杂度也就几种:
执行的效率从上往下递减
前面已经举过O(n) 和O(n²)，我们再讲讲O(1)和O(logn)
1. O(1)
1 int a = 1;
2 int b = 1;
就比如上面这段代码，它的时间复杂度就是O(1),注意不是O(2),也就是只要代码的执行实际不随着n的增长而增长，也就是基本上方法内没有循环递归这样的语句，即使你一个方法有几千行代码，时间复杂度就是O(1)。
2. O(logn)
1 int i= 1;
2 while( i <= n) {
3 i = i * 2；
4 }
对数阶的时间复杂度啊，相对而言是最难分析的。不过问题不大让我们来深入理解一下！
咱们看看上面的变量i，它的初始值是1，每次循环之后就乘2，这就完全符合我们学过的等比数列：
初始值是1 那就是2º , 2¹ , 2² ...... 。最终2的x次方等于n而这个x其实就是我们运行的次数，你看看是这样的吧。所以,时间复杂度就是O(
)！
那我们循环不乘2，咱们乘3那时间复杂度是不是就是O()？
实际上，咱们不过底数是多少，我们对于对数阶的时间复杂度都记为O(),因为对数之间是可以互相转换的
，提取出常数之后O(
) = O(常量*
)，所以我们统一记为O(
)！
再更细一点，时间复杂度还分:最好情况时间复杂度、最坏情况时间复杂度，平均情况时间复杂度，均摊时间复杂度。
来上代码！
1 int find(int[] array,int x) {
2 int result = -1;
3 int n = array.length;
4 for(int i = 0 ;i < n; i++){
5 if(array[i] == x){
6 result = i;
7 break;
8 }
9 }
10 return result;
11 }
最好的情况就是查的这个x在数组的第一个位置！所以最好情况时间复杂度就是O(1)。
最坏的情况就是查的这个x在数组的最后一个位置或者没查到！这两种情况都遍历了整个数组，所以最坏情况时间复杂度就是O(n);
但是这两种都太极端了，我们来平均一下，简单点假设x在这个数组里面的概率为,那不在这里面的概率也是
，如果在数组里的话，在0到(n-1)之间每个位置的概率就是
。所以我们可以推导出公式:
在按照我们之前说的省略一下常数，平均情况时间复杂度就是O(n)。
一般情况下，正常的时间复杂度就已经够我们用的了！除非在这三种情况下，时间复杂度有量级的变化，我们才会以这三种情况来区分！
咱再来了解一下更高级的玩意！均摊时间复杂度，这东西比我们上面说的那三种用到的更少了。
听起来好像和平均情况时间复杂度有点像，但是不太一样。就比如ArrayList，我们知道ArrayList底层是数组实现了，数组是有固定大小的设为n，正常情况下我们的插入数据的时间复杂度是O(1)。
如果我们自己实现了一个ArrayList,在扩容时没有调用System.arraycopy()，而且自己new一个新的数组，大小为之前的2倍，并且用for来拷贝的话(不推荐，效率比System.arraycopy()低，只是为了说明均摊时间复杂度!)。
所以扩容的时候我们需要搬迁以前的n个数据的到新的数组上，这一次操作的时间复杂度就是O(n),然后之后一段时间内我们插入的时间复杂度又是O(1)。就只要往复又到扩容然后正常插入。。。。。循环。
我们总结下这种规律，在O(n)插入之后都伴随着n次的O(1)插入，那我们把n平均的分到每次O(1)插入上，那均摊下来是不是几乎所有的插入的时间复杂度都是O(1)了呢？这就是均摊时间复杂度，一般的均摊时间复杂度都等于最好情况时间复杂度！
空间复杂度
空间复杂度的全称是渐进空间复杂度(asymptotic space complexity)，表示算法的存储空间和数据规模的增长关系。
同样咱们先看一段代码
1 int i= 1;
2 int[] a = new int[n];
其实和时间复杂度分析是一样的，第一行代码申请了一个存储变量i，第二行申请了n个大小的int类型数组，因为第一行是常量，所以忽略，只看第二行，所以得出空间复杂度就是O(n)。
而且常见的空间复杂就是O(1), O(n), O(n²)，想对数阶的都很少遇到，而且具体分析的也比时间复杂度简单多啦！
总结
理解了这两种复杂度分析等于我们掌握了代码中的“时间”和“空间”能力！有点厉害哈哈哈。
如果有错误欢迎指正！以下是我的个人公众号！请大家多多支持谢谢！
网友评论