复杂度分析

  复杂度分析是算法中非常重要的一点，只有做了复杂度分析才能判断自己目前选择的方案是否是最适合 了，所以我们应该花一些时间在理解的基础上去掌握如何分析一段代码复杂度 时间复杂度 概念：时间复杂度全称为 渐进时间复杂度，表示算法的执行时间与数据规模之间的增长关系。 几种常见的时间复杂度有 O(1) O(n) O(logn) O(nlogn) O(n²) O(n*) *可以任意正数 复杂度的完整公式为T(n) = O(f(n)) 表示随着执行次数n的增加，执行时间也成正比的增加，f函数就是 上面的这些种类 当你的程序中没有循环，只会从头到底执行一次， 时间复杂度就为O(1),你会说那我不止一行代码呀，真 实是O(4)，没关系，时间复杂度是一个随着n增长的时间的粗略计算，这里没有循环，可以忽略 为 O(1) 当你的程序有一个n次的循环，那么时间复杂度就是 O(n)，下面例子真实执行时间为 O(n+2)头尾两行,但 随着n的增长，2是可以忽略的，所以我们会归为O(n)，和上面忽略为O(1)是一个意思 当循环条件在循环中有乘法级别的运算时 如 i = 2*i 那么循环次数为 log 2 n ，或者其他情况有包括以3 为n的对数等等，时间复杂度都忽略为O(logn)，要知道这个时间复杂度明显是小于 O(n) 的 其他的复杂度依次来类比就知道啦，O(n²) 是有嵌套循环的时间复杂度，O(nlogn)是logn复杂度循环的外 面还有一层n级别复杂度的循环 int cal(int n) { int sum = 0; int a = 1; sum = a + n; return sum; } int cal(int n){ int sum = 0; for(int i = 0;i < n; i++){ sum = sum +i; } return sum; } int cal(int n){ int i = 1; while(i <= n){ i = i *2; } }那么如果代码中有好多种 复杂度级别的代码该如何判断呢？ 答案是以最高时间复杂度为最终结果。 空间复杂度 概念：渐进式空间复杂度，表示算法的存储空间和数据规模之间的增长关系。 常见的空间复杂度 有 O(1) O(n) O(n²) 如下代码，整体申请空间只有 长度为n的数组a 和 整型 i ，i可以忽略，空间复杂度为 O(n) 其他以此类推 最好，最坏，平均情况时间复杂度 分析下这段代码，这个循环看起来时间复杂度像是O(n),元素可能出现在数组中的任意位置，时间复杂度 可能是O(1)，O(2).....O(n),其中O(1) 是最好情况时间复杂度 ，O(n)是最坏情况时间复杂度。那么它的最 终复杂度应该为平均情况时间复杂度 除了上面分析的情况，还有一种情况是不在数组中，（1+2+3+..+n+n）/(n+1) = n(n+3)/2(n+1),在大O标 记法中，可以省略掉系数，低阶，常量，所以这个公式简化后就是O(n) 更加严谨一些，还需要在这个计算公式中引入概率，即每种情况出现的次数，这里假设 在不在数组中的 概率各为1/2 ,0...n 每个的概率为1/n,则他们的实际概率为1/2n, 这个计算公式应该改为 1(1/2n) +2(1/2n)+....n(1/2n)+n(1/2) = (3n+1)/4 ，这个值就是概率论中的加权平均值，也叫作期望值，所以平均 时间复杂度的全称，也叫作加权平均时间复杂度或者期望时间复杂度，这段代码的加权平均时间复杂度 仍然是O(n) 注：只有同一块代码在不同的情况下，时间复杂度有量级的差距，我们才会使用这三种时间复杂度 来区分 void pring(int n){ int i = 0 ; int[] a = new int[n]; for(i;i < n; ++i){ a[i] = i*i; } } int find(int[] array,int n,int x){ int i = 0; int pos = -1; for(;i<n;++i){ if(array[i] == x){ pos = i; break; } } return pos; }均摊时间复杂度 假如数组长度为n，上面的例子就是判断当前插入个数，是否已经占满了数组，如果数组已满，循环n 次，得到数组的和，并清空数组，如果没满，直接插入，分析一下，大多数情况 （n-1）时间复杂度为 O(1)，最后一次时间复杂度为O(n),所以我们均摊一下，时间复杂度就是 O(1) ，这就叫做均摊时间复杂 度，均摊时间复杂度一般是最好时间复杂度 整理自《数据结构与算法之美》 int[] array = new int[n]; int count = 0; void insert(int val){ if(count == array.length ){ int sum = 0; for(int i=0;i<array.length;++i){ sum = sum + array[i]; } array[0] = sum; count = 1; }else{ array[count] = val; ++count; } }