碱对数的时间复杂度的算法 [英] base of logarithms in time-complexity algorithms

问题描述

什么对数在所有的时间复杂度算法的基础？它是基地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.

这篇关于碱对数的时间复杂度的算法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！