算法

小到Sorting或Searching,大到AI,算法统治着一切!

suanfa

小学数学中的竖式计算,就是一个算法...

Algorithm is a procedure of finite steps to solve problem in an efficient way hopefully. Take algorithm as a technology!

sequence, if...else..., loop, AND recursive!

Base --> Divide --> Conquer --> Combine,Divide-and-Conquer算法之所以有可能将时间复杂度几乎降低一个维度(将一个\(n\)变为\(\log{n}\)),是因为将待解决的问题divide到最后,Base部分(watershed function)的时间复杂度为\(\Theta(1)\)。不过这并不绝对,要具体分析,与如何divide,以及如何Combine(driving function)都有关系。

Merge Sort快的原因是,它的divide总是平衡的。平衡就意味着用最少的conquer(recursive call)层数,就能到达base。许多算法的worst case,都来自于极不平衡的divide。虽然不平衡的divide,也可以用\(\Theta(\log{n})\)来统一概括conquer层数,但不够tight,越不平衡,hidden constant就越大。

Divide之后自然就是Recursive,如果在不同的Divide中,存在相同的Subproblem,避免重复计算也是正常策略,这就是Dynamic Programming!

P, NP, NPC, NP-hard:

-- 目录[6] --

-- 文章[21] --