博客

没有宏观的架构设计，没有特定的框架语言。在


Codility


提出的一些小问题上，用最纯粹的方式测试你最基本的编码能力。

Codility第一课：算法复杂度

---

各种算法书的开篇大多是算法分析，而



复杂度(complexity)



又是最基本的分析指标。所以

Codility的第一课

也不例外，直入复杂度主题。这里不再详述其概念，而只提及复杂度的几个注意点：

1. 复杂度不是程序运行时间的准确度量，而是数量级。
2. 重点是找到
   
   
   
   主要因子操作
   
   
   (dominant operation)
   
   
   
   ，忽略常量以及数量级更低的项，可理解为求极限。
3. 谁是dominant和有几个dominant都依赖于输入数据的规模，例如数据大小、矩阵大小或某个入参的值。
4. 分析复杂度时，我们必须要看能使程序长时间运行的最坏情况。

例如，下面的源程序中，

dominant就是第四行

的操作，

它会随着入参n的不同而反复运行多次

。于是程序的总操作数可能是c*n + a。但前面说过，我们会

忽略常量只看数量级

。因此，这段代码的复杂度就是O(n)。在不同的编译器或硬件平台上，具体运行时间会各不相同，可能是20*n + 1，也可能是½*n + 3，但绝不可能是n²。另外，若循环体内有跳出条件那么程序可能会提前终止，但我们说过，复杂度

必须看最坏情况

。至此，上面列举四点已都符合。

常见的复杂度示例程序如下。值得注意的是，至此我们其实一直在讨论的是执行操作步数的数量级，即时间复杂度。对于



空间复杂度(space complexity)



来说，其实度量方法也都是一样的。如果你的代码中使用了常数个数的变量，那么空间复杂度就是O(1)，如果你使用了长度相关于输入数据大小n的数组，那么你的空间复杂度就是O(n)。

Codility使用体验

---

Codility的课程简洁明了，而测验界面也是很简单易用的，可以选择各种编程语言，甚至题目也针对一些语言做了国际化。还可以自由添加五个测试用例，检验你的代码是否能编译、运行通过。但复杂度和正确语法无从得知，确认好后提交即可。