min*_*gus 2 sorting algorithm search asymptotic-complexity computer-science-theory
这个问题是关于导致出现登录问题(例如排序和搜索)的解决方案之间是否存在一些抽象的相似性.或者,更简单地说,为什么日志在算法复杂性中如此频繁出现？
当一个问题可以通过乘法因子反复减小时,通常会出现对数.根据定义,将问题减小到恒定大小(例如,大小1)需要对数的步骤.
一个典型的例子是重复消除一半的数据集,就像二进制搜索一样.这给了O(log2(n))复杂性.一些排序算法通过将数据集重复分成两半来工作,因此在时间复杂度上也具有对数项.
更一般地说,对数经常出现在分而治之的复发关系的解决方案中.有关进一步的讨论,请参阅维基百科中的Master Theorem.