在计算复杂度时，我们通常会用O(n)/O(nlogn)来表示。那么究竟什么是大O呢？
其中a、b、c、d表示常数，是固定不变的。换句话说，随着数据规模n的不断增大，算法效率的改变和a、b、c、d常数的关系是不大的。而和logn、n、nlogn、n^2关系巨大，所以我们通常省略常数项。
比如下面这个例子，算法AO(n)所需执行指令数是10000*n，而算法BO(n^2)所需执行指令数是10*n^2。
而且通过这张图我们可以很好的理解，随着输入数据量的增大，他们的增长速度是完全不同的。
相信现在大家对O(n)已经有了初步的认识，那么我们来看O(n)更严格的定义。在学术界，严格来讲，O(f(n))表示算法执行的上界。什么叫「算法执行的上界」呢？
而在实际情况中，也存在这种情况的复杂度：O(AlogA+B)，而A和B是没有关系的。这个时候，我们就不能合并算法复杂度。
你可能会想，这个问题还不简单
1、每一个字符串按照字母序排序：每一次排序都是nlogn，一共有n个字符串，所以是n*nlogn2、之后再将整个字符串数组按照字典序排序nlogn
把他们相加起来，O(n*nlogn+nlogn)=O(n^2logn)
很遗憾，这个想法是错的。
首先，「这个字符串」的长度和「整个字符串数组」混在了一起，他们是没有关系的。所以，我们需要将这两个参数拆开。假设最长的字符串长度为s；数组中有n个字符串。对每个字符串排序：O(slogs)。将数组中的每一个字符串按照字母序排序：O(n*slog(s))
快速排序算法，最差的情况是O(n^2)，最好的情况是O(nlogn)。但我们把排序算法的复杂度约定为O(nlogn)，因为对于平均情况来说，他的复杂度就在这个。
为了让大家对对数据规模有一个概念，在这里我们用程序来说明。运行一个O(n)的程序，n的取值从1、10……10^9。
如果你想要在1s之内解决问题：
O(n^2)的算法可以处理大约10^4级别的数据，O(n)的算法可以处理大约10^8级别的数据，O(nlogn)的算法可以处理大约10^7级别的数据，因为lg10^7约等于7。
那么在面试中，我们就可以根据数据规模大致估算算法的复杂度。如果面试管说，我的数据规模是10^8级别。那就可以确定，算法复杂度基本是O(n)。（当然有的时候O(nlogn)也是可以的，这是因为logn是复杂度非常低的一个级别，处理速度也是非常快的。）
如果面试官提示说，我们这个算法只需要处理10^3的数据。这个时候给我们留下了足够的空间，设计一个O(n^2)的复杂度就可以满足要求。
constsum=(n)=>{if(n===0){return0;}returnn+sum(n-1)}空间复杂度：O(n)递归调用的深度是n，我们的系统栈中需要压入n个状态。换句话说，在整个递归调用中，递归的深度是多少，我们的空间复杂度就是多少。
functionswapTwoNumbers(a,b){lettemp=a;a=b;b=temp;}在这个算法中没有数据规模的变化，也就是常数级别的算法，所以算法复杂度是O(1)
严格地讲，这个算法执行的指令数和数据复杂度是成n^2比例关系的。
来看看minIndex=j执行了多少次。
比如大家都很熟悉的二分查找法：
//把number转换为string的操作：functionnumberToString(num){lets=""while(num){s+='0'+num%10;num/=10;}reverse(s)returns;}仔细看这个算法，它的复杂度相当于：n经过几次“除以10”操作后，等于0？经过上面的学习，我们很快可以得到答案log(10)n=O(logn)
上面我们说过，看到双重循环，基本可以断定为O(n^2)级别的算法。但是也有特例，比如下面这个：
无论是归并排序还是快速排序，都用到了递归算法。
由于这两个算法复杂度都是O(nlogn)级别的，刚接触算法的时候，你可能会认为递归算法的复杂度就是O(nlogn)。
当然这个结论是不对的，一定要具体问题具体分析。
第一种情况很简单，我们只会进行一次递归调用。
最典型的例子就是二分查找：
再比如：计算0-n的和
此时我们应该关系计算调用的次数。
functionf(n){if(n===0){return0}returnf(n-1)+f(n-1)}通常，我们可以画一颗递归树，比如f(3)时：
所以，我们要想知道f(3)调用了多少次，只需要数树上的节点就可以了。
1+2+4+8=15
2^0+2^1+2^2+2^3+……+2^n=2^(n+1)-1
复杂度O(2^n)
这其实是一个等比数列的求和公式。经过计算之后，它的结果是2的N次方级别的数字。换句话说，这个算法，它每次都两次自己调用，自己调用，两次递归函数。最终，我们得到了一个指数级的算法。
请注意，指数级的算法是一种非常慢的算法。如果你设计出了一个指数级的算法，就一定要小心。比如说N在20左右，就是百万级的计算量了。如果N在30的时候，普通的计算机转起来就已经非常慢了。其实你是可以对这种进行优化的，比如说进行剪枝操作，再比如说有些指数级算法，可以转化为动态规划等等其他的方法。这样我们就把一个指数级的算法问题，转换成一个多项式级别的算法问题。
functionmergeSort(arr,l,r){if(l>=r){return;}letmid=(l+r)/2mergeSort(arr,l,mid)mergeSort(arr,mid+1,r)merge(arr,l,mid,r)}这是因为在我们之前所举的例子中，我们整棵树的深度是N，而在这些排序搜索中，我们这些树的深度其实是logn的。
那么归并排序、快速排序的算法复杂度是怎么计算的呢？
在这些排序算法中，我们在每个节点中处理的数据规模是逐渐缩小的。而我们之前的例子，每一个节点所处理的数据规模都是一样的，虽然他们都是1，那么大家可以看在右侧，我就画出了。对于归并排序算法，我们要排序8个数字的时候，递归树的形状是怎么样的。
当我们的数组长度为8时，节点树如下：一共logn层，对于每一层的节点，又是O(n)级别的算法。所以，总的算法复杂度是O(nlogn)
在根的地方，我们要处理8个元素，之后，一分为二，每个节点处理四个元素，再一分为二，每个节点处理二个因素，最后一分为二，每个节点处理一个元素，一个元素的时候，我们就不用处理了，因为1个元素不用排序。
那么在我们有8个元素的时候，首先这棵树它的层数不是八层，而是三层。而且每一个节点所处理的数据规模是越来越小的。
那么，这个nlogn怎么来的呢？我们一共有logn这么多层。
所以总体来说，在每一层上，我们处理的数据量也是O(n)这个级别一共有logn层，把它们相乘就得出了onlogn。