举个简单的例子,评判一个算法的时间复杂度,那么下面 C 语言代码的复杂度是多少呢?
i = 1;
while( i < n ){
i = i * 2;
}
对于此段代码来说,我们只需要求出 while 循环中代码(也就是第 3 行代码)执行的次数,即可轻松得到这段代码的时间复杂度。可以看到,循环条件为 i<n,而变量 i 的值每经历一次循环都会翻倍,因此假设有一个临界值 m,能恰好使 2m = n,此时循环将会终止,程序运行结束。
求这段代码的时间复杂度,只需要求出 m 的值即可。这就需要我们具备对数运算的能力。此时,如果读者无法理解 m 值的由来,就需要恶补一下关于数学中对数运算的相关知识。
当然,对于绝大多数的数学运算,也可以借助计算器或者网络工具来计算得出。事实上很多工作,我们完全不必亲力亲为,要善于运用网络来解决遇到的难题。在实际开发中,很多网站都能提供帮助,例如 C++ 中可以使用 STL 标准库,Python 中可以使用 collections 模块等等。这意味着,我们的项目变成了已封装好的模块的组合应用,只需简单了解各个模块,即可实现最初的目的。