什么对数在所有的时间复杂度算法的基础?它是基地10或以e为底?
What is the base of logarithm on all time-complexity algorithms? Is it base 10 or base e?
当我们说的平均值排序复杂度为O(n log n)的。是log N 10或电子邮件的基地?
When we say that the average sorting complexity is O(n log n). Is the base of log n 10 or e?
推荐答案在计算机科学,它往往立足2.这是因为许多分而治之,表现出这种复杂性是在每一步划分问题有两种算法。
In Computer Science, it's often base 2. This is because many divide and conquer algorithms that exhibit this kind of complexity are dividing the problem in two at each step.
二进制搜索是一个典型的例子。在每一步中,我们把数组分为二,并在半一只有递归搜索,直到你到达一个元素(或零元素)的子数组的基本情况。当除以长度 N 的阵列中的两个,师达到一个元素的数组前总数 LOG2(N)。
Binary search is a classic example. At each step, we divide the array into two and only recursively search in one of the halves, until you reach a base case of a subarray of one element (or zero elements). When dividing an array of length n in two, the total number of divisions before reaching a one element array is log2(n).
这是经常被简化,因为在讨论算法分析时,不同碱基的对数实际上等效。
This is often simplified because the logarithms of different bases are effectively equivalent when discussing algorithm analysis.
更多推荐
碱对数的时间复杂度的算法
发布评论