Java 什么是时间复杂度以及如何找到它？

What is time complexity and how to find it?

提问by Ilja

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.

我已经阅读了很多资源，但仍然无法理解什么是时间复杂度。我阅读的资源基于各种公式，我知道这O(n)是用来表达时间复杂度的，但我不知道如何。任何人都可以请以可理解的清晰方式向我解释这个原则。

采纳答案by Vinayak Pahalwan

Reference: How to Calculate Time complexity algorithm

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

I found a good article related to How to calculate time complexity of any algorithm or program

我找到了一篇关于如何计算任何算法或程序的时间复杂度的好文章

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:

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

statement;

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

是恒定的。语句的运行时间不会随N发生变化。

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

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

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

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

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.

是二次的。两个循环的运行时间与N的平方成正比，当N加倍时，运行时间增加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;
}

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.

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

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

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.

是N * log ( N )。运行时间由 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 ( ) 其中是度量。快速排序算法将被描述为O ( N * log ( N ) )。

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. ;)

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

Edit:

编辑：

Now the Question is how did the log nget into the equation:

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

1. For each step, you invoke the algorithm recursively on the first and second half.
2. Thus - the total number of steps needed, is the number of times it will take to reach from n to 1 if you devide the problem by 2 each step.

1. 对于每个步骤，您在前半部分和后半部分递归调用算法。
2. 因此 - 所需的总步数是如果您将问题每一步除以 2，则从 n 到 1 所需的次数。

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)

等式是：n / 2^k = 1。由于 2^logn = n，我们得到 k = logn。所以算法需要的迭代次数是O(logn)，这将使算法O(nlogn)

Also, big Onotation 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.

此外，大 O符号使我们易于计算 - 平台无关的近似算法将如何渐近（在无穷大），它可以将算法的“家族”划分为其复杂性的子集，并让我们轻松地在它们之间进行比较。

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

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

回答by Deepu

You should also read about Amortized Analysisto fully understand the notions of time complexity. Amortized analysis is used to have a worst-case bound for the performance of an algorithm by considering all the operations.

您还应该阅读 aboutAmortized Analysis以完全理解时间复杂度的概念。摊销分析用于通过考虑所有操作对算法的性能进行最坏情况的限制。

The link to the Wikipedia article is given below,

下面给出了维基百科文章的链接，

http://en.wikipedia.org/wiki/Amortized_analysis

http://en.wikipedia.org/wiki/Amortized_analysis