在结果的O符号和分析方式上,你们认为哪些算法的复杂度分析非常惊人(复杂、奇怪)?
在结果的O符号和分析方式上,你们认为哪些算法的复杂度分析非常惊人(复杂、奇怪)?
我有(相当)多的例子:
2D有序搜索分析非常有趣。你有一个数字数组NxN,其中每行从左到右排序,每列从上到下排序。任务是在数组中找到特定的数字。
递归算法:选择中间元素,与目标数字进行比较,丢弃四分之一的数组(取决于比较结果),对剩余的三个四分之一应用递归,这种算法非常有趣。
在编程方面,我倾向于选择非确定多项式复杂度,特别是考虑到它可能与多项式相同(尽管可能性很小)。同样,在理论上可以从量子计算中受益的任何事情都会得到我的认同(注意:这个集合并不是所有算法)。
另一个得到我的认同的是针对任意精度数的常见数学运算 - 在这里你必须考虑乘以大数比乘以小数更加费时。 Knuth对此进行了相当多的分析(这对任何人来说都不是新闻)。Karatsuba方法十分巧妙:通过数位将两个因数切成一半(A1;A2)(B1;B2),然后分别计算A1 B1、A1 B2、A2 B1、A2 B2,最后将结果组合起来。如有需要,可进行递归处理...