算法-复杂度分析
标签:算法

复杂度分析

1. O

n表示数据规模

O(f(n)) 表示运行算法所需要执行的指令数,和f(n)成正比。

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

  1. 假设最长的字符串长度为s;数组中有n个字符串

  2. 对每个字符串排序:O(slogs)

  3. 将数组中的每一个字符串按照字母序排序:O(n*slog(s))

  4. 将整个字符串数组按照字典序排序:O(s*nlog(n))

  5. O(nslog(s)) + O(snlog(n)) = O( nslogs + snlogn )

    ​ = O( ns(logs+logn) )

2. 数据规模的概念

如果要想在1s之内解决问题:

O(n^2)的算法可以处理大约10^4级别的数据;

O(n)的算法可以处理大约10^8级别的数据;

O(nlogn)的算法可以处理大约10^7级别的数据

3. 空间复杂度

多开一个辅助的数组:O(n)

多开一个辅助的二维数组:O(n^2)

多开常数空间:O(1)

4. 递归算法的复杂度分析

不是有递归的函数就一定是O(nlogn)!

4.1 递归中进行一次递归调用的复杂度分析

二分查找每次都是一半一半的向下查找,递归的深度的为logn,最后的时间复杂度也就为O(logn)。

上面进行的是计算前n项和。

上面这个是就是x的n次方,但不能计算负数的情况,每次递归去求n/2次方,注意要对计算机的奇数的处理操作。

4.2 递归中进行多次递归调用

上面进行的是在f中将两次调用f(n-1),此时我们应该关心的是调用的次数,可以通过画一棵递归树来看,可见对于f(3)将两次调用f(2),每个f(2)两次调用f(1)...,因此要计算f(3)递归调用了多少次,就需要数这棵树上的节点个数。即1+2+3+4=15,一般的话就是2^(n+1)-1,这个结果是O(2^n)的算法,对于20左右已经是百万级别的了。

对于归并排序,在根节点的时候,我们要处理8个元素,后面是4个元素,依次类推,我们一共有logn层,每次都要处理n个元素

5. 均摊复杂度分析(Amortized Time)

动态数组,每次添加一个元素都是O(1)的复杂度,当添加到当前数组能容纳的最后一个元素时,将会发生resize操作,此时为O(n)时间复杂度,前面的n次加起来为n,和最后一次的n,相当于2n,均摊下来还是O(1)的时间复杂度。

对于删除元素,可能会发生复杂度震荡,当删除到一个元素后,数组的元素个数变为一半,此时应该resize,但如果下一个是继续添加元素的话,将会再次发生resize操作,如此进行,复杂度将不再是O(1)的了,所有应当在元素个数变为数组容量的1/4的时候,在进行resize操作,为接下来的添加元素留出足够的空间。

  • 4 min read

CONTRIBUTORS


  • 4 min read