「干货笔记」算法评价与复杂度
在算法竞赛中，一道好的算法竞赛题目可以通过对一个程序评分，区分出「好的算法程序」和「不那么好的算法程序」。而评价一个算法，也有着一定的计算模式和标准。利用这个标准，就可以评价一个算法程序是否优秀——从而预判这个算法的可靠程度，并作出调整和优化。
如何去评价一个算法？
算法竞赛中，为测试一个选手的程序，一般采用的是「黑箱测试法」：即在进行测试时，将程序看作是一个不能打开的「黑盒子」。只需将输入数据扔进这个黑盒子里，观察它返回的结果是否正确，至于程序内部如何实现则并不关心。
对于算法竞赛的评价机制来说，选手需要在规定的时间内实现题目所要求的程序，且程序须在限定的时间与内存之内给出测试数据所对应的答案。于是，对选手的程序就有了以下要求：
代码可实现
即能够将算法通过代码实现出来。如果能想出一个算法却无法实现，或者是不能在比赛限定的时间内将其实现，都是不符合要求的。
结果需正确
程序需要能够正确运行并输出正确的结果，才能通过题目的测试点。
运行不超时
除了需要结果正确，运行用时应当越短越好。对于数据量大的题目，需要尽力去优化程序运行用时，否则将难以通过测试点。
资源不超限
一台计算机的运算资源是有限的，所以资源占用也应当越少越好。
显而易见，前两点是作为一个合格程序的前提。对于一个算法，更重要的则是它的时间复杂度。
什么是时间复杂度？
在实际测试之前，一个程序是无法准确估计其运行时间的。但是，几乎所有的算法竞赛的题目中都会明确地告知将输入数据的规模和运行时间的限制。而选手就可以通过分析算法的时间复杂度，从而预计是否能够在限定的时间内运行完算法程序。下面是一个简单的例子：
例题 质数是指除了1和本身之外没有其他约数的数，如7和11都是质数，而6不是质数，因为6除了约数1和6之外还有约数2和3。给定n个正整数a，输出质数的个数。对于所有测试数据，0<n≤200，0<a≤10⁸.。
例如，当输入是
应当输出 2
子任务1 (10分)：n≤1, 0<a≤10⁸.
子任务2 (30分)：n≤200, a≤10*
子任务3 (60分)：n≤200, a≤10⁸
思路1： 最直接的思路就是枚举所有a可能的因数，代码十分的简单：
那么，这个程序运行需要多久呢？程序的运行时间和输入的数据 a 有关，毕竟数据越大，计算的时间就越长。不过现在，可以通过分析这一份代码估计它要运行多少次语句。
在这里，当 a 较大时， if(a%j==0) 这条判断语句就要运行很多遍。对于某一语句，计算需要运行多少次时，可以在这条语句后加上一个全局计数器变量，每运行一次就自增1，最后输出这个计数器即可得到这条语句的运行次数。
当然，亦可通过数学推导的方式得到这个数据。十分明显的，对于单个数 a ，这个算法最多枚举的次数应为 a-2 ，我们把算法需要执行的运算次数用函数表示，即 T(a) =a-2 。此时为了估算算法需要的运行时间和简化算法分析，我们引入时间复杂度的概念。
定义：存在常数 c 和函数 f(N)，使得当 N >= c 时 T(N) <= f(N)，表示为 T(n) = O(f(n)) 。
当 N >= 2 的时候，f(n) = n^2 总是大于 T(n) = n + 2 的，于是我们说 f(n) 的增长速度是大于或者等于 T(n) 的，也说 f(n) 是 T(n) 的上界，可以表示为 T(n) = O(f(n)) 。
因为 f(n) 的增长速度是大于或者等于 T(n) 的，即T(n) = O(f(n)) ，所以我们可以用 f(n) 的增长速度来度量 T(n) 的增长速度，所以我们说这个算法的时间复杂度是 O(f(n)) 。
算法的时间复杂度，用来度量算法的运行时间，记作: T(n) = O(f(n)) 。它表示随着输入大小n 的增大，算法执行需要的时间的增长速度可以用 f(n) 来描述。
拿到算法的执行次数函数 T(n) 之后，怎么得到算法的时间复杂度呢？
在执行次数中，常数项对函数的增长速度影响并不大，所以当 T(n) = c，c 为一个常数的时候，这个算法的时间复杂度就为 O(1)；如果 T(n) 不等于一个常数项时，即直接将常数项省略。
例如，对于 T(a) =a-2 ，其时间复杂度即为 O(a)。
其次，高次项对于函数的增长速度的影响是最大的，故而直接忽略低次项。
例如，在 T(n) = n^3 + n^2 + n + 114 中，n^3 的增长速度是远远大于 n^2 的，对于 n 同理，时间复杂度就为 O(n^3)。
而且，因为函数的阶数对函数的增长速度的影响是最显著的，所以也直接忽略与最高阶相乘的常数。
例如，当 T(n) = 3n ^ 514时，时间复杂度为 O(n^3)。
总而言之：如果一个算法的执行次数是 T(n)，那么只保留最高次项，同时忽略最高项的系数和常数后得到函数 f(n)，此时算法的时间复杂度就是 O(f(n))。
回到 T(a) 上来，这个算法的时间复杂度即为 O(a)。但是，这一段代码的执行次数也与 n 有关。在 子任务2 的情况下，最多将运算 200*10* = 2x10⁸ 次。在一般的家用计算机，每秒可以进行数千万到数亿（10⁸数量级）的运算。所以，这个算法的运算次数是十分危险的，子任务3是的。
思路2： 不如试着去砍掉多余的枚举次数？可以先将所有2以外的偶数砍掉，且可以发现偶数以及大于 a/2 的因数枚举都是没有必要的：
可以看到，这份代码削减了十分多的枚举次数，但仍应按最坏的结果计算，可以得到 T(a) = (a/2-1)/2 ，时间复杂度仍为 O(a) 。计算次数约为 1x10⁸ ，应可通过子任务2，但对于子任务3则远远不够——将运算 1x10⁹ 次。
思路3： 还能再快一点吗？事实上，枚举到 √a 就足够了，可以大大地减少枚举次数：
此时，T(a) = (√a-1)/2 ，时间复杂度则为 O(√a)。这样，只需运算 2x10* 次即可，已经可以完全胜任这道题目。
当然，还有更快的方式！——
大于3的质数有一个特点，即总是等于 6x-1 或者 6x+1 （x为正整数），所以只需以6为步长枚举因数就可以减少很多工作量。当然，还有很多更高效的算法，这里就不再赘述。
不难看出，数据量越大，用时也就越多。而在不同的算法下，不同的时间复杂度随数据量的增长是不一样的：有的算法对数据量的增长是十分敏感的，例如 O(n³) 或 O(2ⁿ) 甚至是 O(n!) ，后两者即使 n 只有几十，运算次数就已经达到了天文数字，这也是很多搜索回溯算法不能处理稍大规模数据的原因；有的算法则对数据量增长不敏感，例如 O(n log n) 或是 O(n) ，一些人类高质量算法甚至可以接近于常数级复杂度。以下则是一些常见的时间复杂度量级，按执行效率从高到低排列：
常数阶O(1)
对数阶O(log N)
线性阶O(n)
线性对数阶O(n log N)
平方阶O(n²)
立方阶O(n³)
K次方阶O(n^k)
指数阶(2ⁿ)
到了这里，其实运行速度还可以再快一点，不过——应当优化的在于输入部分。
使用cin读入的速度比较慢，而使用scanf读入可以加快速度（复杂度不变），这在需要输入大量数据时尤为明显。
两者区别在于，使用scanf输入元素时，作为一种格式化输入，已经提前告知输入的数据类型，而不需要每次输入时判断元素类型；而用cin输入数据时须每次判断数据类型，作为一种字符流输入，需要先存入缓冲区再输入，故而速度较慢，但可以保证读入的安全性。
当然，也可以自己实现一些「快速读入」的方法，例如用 getchar 等实现数据输入以加快读入速度。而这些不改变算法复杂度但可以加快程序运行速度的方法被称为常数优化。（当然，常数优化的方法还有很多，例如内存优化等）
实际上，O(n) 算法相对于 O(n log n) 算法的效率并没有 log₂n 倍提升，且在数据量越多时优势越小，这是因为 O(n) 算法的执行次数 T(n) 还带有常数 k （难以用定量来求出，但程序执行的语句的越多，k就会越大），从而抵消了和对数级别算法的优势。对于小规模数据，常数对于运行时间的影响并不大；而当数据规模规模较大时，就不能不考虑常数带来的影响。
对于一个进阶的选手来说，常数优化是一项十分重要的技能。浅举一例：当 n=1000 时，0.01n<100n log₂ n ，在数据量并不大的时候，努力优化并降低一个高复杂度算法的常数，比一些大常数的低复杂度算法常常运行得要更快。下面是一个快速读入整数函数的例子：
『还有更多常数优化的方法，这些将在以后讲到』
事实上，无论测试数据规模有多小，运行一个程序仍需要数毫秒的时间。因为在运行程序前，需要一些时间进行初始化工作，例如分配内存资源等，而这些初始化的时间与数据规模无关。如果一种算法的运算次数与数据规模无关，则它的时间复杂度是常数级别的，即 O(1) 。一些算法不使用循环语句，而是使用一些公式计算答案，这些可能就是 O(1) 复杂度的算法。
通过以上的例子，大家应该都明白并了解了什么是时间复杂度以及计算时间复杂度的方式，并且可以使用时间复杂度作为评价算法效率的一项重要参考指标。一些算法或者程序设计竞赛的题目会给出测试数据规模不等的子任务，从中我们可以看出题目要求的复杂度，并根据这些信息以选择合适的算法，尽可能多地通过各个测试点。不过不幸的是，时间复杂度并不能充当你的应急食品（）。
空间复杂度有什么作用？
说到空间复杂度，作为评价一个算法的优秀程度的另外一个重要标准，它与算法程序占用内存空间的大小有关。比起时间复杂度，空间复杂度往往并不怎么受到关注。多数情况下内存的限制一般是几百兆字节，还是比较宽松的，而这并非说明内存空间可以随意敞开了用：只要内存使用超过了上限，即便在规定的时间里给出了正确的答案，亦是不能得分的。所以，除了注意算法的运算效率，还需要关注程序的内存使用是否超限。
一个程序的空间复杂度是十分容易估计计算的。设立数组、使用STL容器储存内容、调用递归函数、创建动态对象等都会占用内存，其中设立数组最容易计算内存空间的占用。
例如，一道题目设定的空间上限为 128MB ，一个 int 数据使用4个字节的内存，理论上则可以存下32000000个 int 类型的数字。显然，一般读入并储存数据所占用的空间大小与数据的规模是呈线性关系的，空间复杂度为 o(n) 。而内存占用亦可以进行常数优化，在答案正确的前提下降低内存空间的使用，从而控制程序运行内存不超限。
再例如，输入数据的规模是n，而需要建立一个 nxn 大小的二维数组储存时，空间复杂度就为 O(n²) 。计算一下，可知128MB的内存最多能够储存 5600x5600 的 int 二维数组（实际仅计算常数访问次数，巨大的时间复杂度亦会导致其用时过长），故而应当谨慎创建一个 n [100000][100000] 这样的二维大数组，而多维数组则亦应更为谨慎，我们应提前计算规划好需要使用的内存空间，并要防止其超限。
要注意的是，为了增加难度，一些题目也会对内存空间作出严格的限制，甚至限制到只有数兆字节的内存。这些题目往往数据量很大，故而无法设立数组储存，只能够读入数据后当即处理后丢弃，这就对算法和思维的考验更高了。
关于「非完美算法」的那些事
在大大小小的程序竞赛中，每一位选手都希望能够以自己有限的能力水平冲刺更多的分数。一些竞赛中，要求选手的程序必须通过所有的测试点才能获得分数，例如国际大学生程序设计竞赛（ICPC）；而一些竞赛中，则将题目分出数个子任务，按点计分，故而程序仅满足部分测试数据时，也能获得部分的分数，例如全国青少年计算机程序设计竞赛。我们可以通过选择一些适当的策略，以获得高的分数。
当难以作出题目的正确解法时，我们可以 直接摆烂 就部分子任务写出一个「非完美算法」，从而取得尽量多的部分分数。以下是一些方法：
完成小数据范围的高复杂度方法
在一道算法竞赛题目中，每个子任务的数据范围是有梯度的。如果找不到能够符合题意的正解，则可以试着以枚举、搜索等基本低效率算法完成题意。尽管算法时间复杂度高，亦能通过较小数据范围的子任务以取得一定分数。
尝试解决部分的特殊情况
部分的子任务会规定一些特殊的情况，例如树状数据结构退化为链状结构、过于复杂的情况不存在等。此时可以通过针对特殊情况专门解决这些子任务，虽然算法并不符合题意，但对于这些特殊情况是正解，从而可以降低对于题目的思维难度。
在一道题目中可能有数种特殊情况，这时可以针对不同的特殊情况作出对应的算法，而后判断输入数据符合的情况，并通过适当的算法专门解决这些特殊情况，从而灵活获得力所能及的分数。
使用近似算法
近似算法中包括随机算法、启发式搜索等，尽管可能不能够得到正确的答案，但可以得到比较理想的结果，效率也不低。算法选择得当的同时加上一点好的运气，甚至亦能够获得题目分数。如果前两种都走不通时，就可以使用近似算法试试（指不定就撞了大运了呢）
在平时练习的时候不一定非要以通过某一道题目为标的，也可以尝试难度大点的题目，分析观察每一个子任务，通过一些非完美算法以尽可能多的完成它们，并通过各种方法优化算法的复杂度，从而接近甚至完成正解。
到了这里，先 挖个坑 ：
关于常数优化的若干方法
各个STL容器的介绍
（暑期更新）
