什么是时间复杂性以及如何找到它？ [英] What is time complexity and how to find it?

问题描述

我已经阅读了这么多资源，仍然坚持理解时间复杂性。我读过的资源基于各种公式，我知道 O（n）用于表示时间复杂度，但我不知道如何。任何人都可以用一种可以理解的明确方式向我解释这个原则。

I've read through so many resources and still am stuck with understanding what time complexity is. Resources I read were based on various formulas, I understood that O(n) is used to express time complexity, but I don't know how. Could anyone please explain this principle to me in an understandable clear way please.

推荐答案

参考：如何计算时间复杂度算法

我发现了一篇与如何计算任何算法或程序的时间复杂度相关的好文章

最常见计算时间复杂度的度量标准是Big O表示法。这消除了所有常数因子，因此当N接近无穷大时，可以相对于N估计运行时间。一般来说，你可以这样想：

The most common metric for calculating time complexity is Big O notation. This removes all constant factors so that the running time can be estimated in relation to N as N approaches infinity. In general you can think of it like this:

statement;

是常数。语句的运行时间不会改变至 N 。

Is constant. The running time of the statement will not change in relation to N.

for ( i = 0; i < N; i++ )
     statement;

是线性的。循环的运行时间与N成正比当N加倍时，运行时间也加倍。

Is linear. The running time of the loop is directly proportional to N. When N doubles, so does the running time.

for ( i = 0; i < N; i++ ) {
  for ( j = 0; j < N; j++ )
    statement;
}

是二次方。两者的运行时间循环与N的平方成正比。当N加倍时，运行时间增加 N * N.

Is quadratic. The running time of the two loops is proportional to the square of N. When N doubles, the running time increases by N * N.

while ( low <= high ) {
  mid = ( low + high ) / 2;
  if ( target < list[mid] )
    high = mid - 1;
  else if ( target > list[mid] )
    low = mid + 1;
  else break;
}

是对数。算法的运行时间与N可以除以2的次数成正比。这是因为算法将工作区域与每次迭代分成两半。

Is logarithmic. The running time of the algorithm is proportional to the number of times N can be divided by 2. This is because the algorithm divides the working area in half with each iteration.

void quicksort ( int list[], int left, int right )
{
  int pivot = partition ( list, left, right );
  quicksort ( list, left, pivot - 1 );
  quicksort ( list, pivot + 1, right );
}

N * log（N）。运行时间由对数的N个循环（迭代或递归）组成，因此算法是线性和对数的组合。

Is N * log ( N ). The running time consists of N loops (iterative or recursive) that are logarithmic, thus the algorithm is a combination of linear and logarithmic.

一般来说，对每个项目做一些事情一维是线性的，对二维中的每个项做某事是二次的，将工作区分成两半是对数的。还有其他Big O指标，如立方，指数和平方根，但它们并不常见。 Big O表示法被描述为O（），其中是度量。快速排序算法将被描述为 O（N * log（N））。

In general, doing something with every item in one dimension is linear, doing something with every item in two dimensions is quadratic, and dividing the working area in half is logarithmic. There are other Big O measures such as cubic, exponential, and square root, but they're not nearly as common. Big O notation is described as O ( ) where is the measure. The quicksort algorithm would be described as O ( N * log ( N ) ).

请注意，这些都没有考虑到最佳，平均和最坏情况的措施。每个都有自己的Big O表示法。另请注意，这是一个非常简单的解释。大O是最常见的，但它也更复杂，我已经展示过。还有其他符号，如大欧米茄，小o和大theta。您可能不会在算法分析课程之外遇到它们。 ;）

Note that none of this has taken into account best, average, and worst case measures. Each would have its own Big O notation. Also note that this is a VERY simplistic explanation. Big O is the most common, but it's also more complex that I've shown. There are also other notations such as big omega, little o, and big theta. You probably won't encounter them outside of an algorithm analysis course. ;)

编辑：

现在问题是如何 log n 进入等式：

Now the Question is how did the log n get into the equation:

1. 对于每一步，您都会递归调用算法


2. 因此 - 所需的步骤总数，如果您将问题的每一步分为2，则从n到达1所需的次数。

等式为：n / 2 ^ k = 1.由于2 ^ logn = n，我们得到k = logn。因此，算法所需的迭代次数为O（logn），这将使算法 O（nlogn）

The equation is: n / 2^k = 1. Since 2^logn = n, we get k = logn. So the number of iterations the algorithm requires is O(logn), which will make the algorithm O(nlogn)

此外，大O 表示法使我们易于计算 - 平台无关近似算法将如何渐近地（在无穷大处）表现，这可以将算法的族划分为其复杂性的子集，以及让我们在它们之间轻松比较。

Also, big O notation gives us easy to calculate - platform independent approximation on how will the algorithm behave asymptotically (at infinity), which can divide the "family" of algorithm into subsets of their complexity, and let us compare easily between them.

您还可以查看此问题以获取更多信息：使用递推方程的程序的时间复杂度

You can also check out this Question for more reading: Time complexity of the program using recurrence equation

这篇关于什么是时间复杂性以及如何找到它？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！