我已经通过谷歌和Stack Overflow搜索，但无处我能够找到一个清楚和直接的解释如何计算时间复杂度。
我已经知道了什么?
比如下面这样简单的代码:
char h = 'y'; // This will be executed 1 time
int abc = 0; // This will be executed 1 time
比如下面这样的循环:
for (int i = 0; i < N; i++) {
Console.Write('Hello, World!!');
}
int i = 0;这将只执行一次。
时间实际上是计算到i=0，而不是声明。
i < N;这将被执行N+1次 i++将执行N次
因此，这个循环所需的操作数为{1+(N+1)+N} = 2N+2。(但这仍然可能是错误的，因为我对自己的理解没有信心。)
好的，这些基本的小计算我知道，但在大多数情况下，我看到的时间复杂度是O(N) O(N²)O(log N) O(N !)等等。
当前回答
这是一篇很好的文章:算法的时间复杂度
下面的答案是从上面复制的(以防优秀的链接崩溃)
计算时间复杂度最常用的度量是大O符号。这样就去掉了所有的常数因子，这样当N趋于无穷时，运行时间就可以相对于N进行估计。一般来说，你可以这样想:
statement;
是恒定的。语句的运行时间不会随着N的变化而改变。
for ( i = 0; i < N; i++ )
statement;
是线性的。循环的运行时间与N成正比，当N加倍时，运行时间也加倍。
for ( i = 0; i < N; i++ ) {
for ( j = 0; j < N; j++ )
statement;
}
是二次。两个循环的运行时间与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;
}
对数。算法的运行时间与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);
}
为N * log (N)。运行时间由N个对数循环(迭代或递归)组成，因此该算法是线性和对数的结合。
一般来说，对一维中的每一项都做某事是线性的，对二维中的每一项都做某事是二次的，将工作区域一分为二是对数的。还有其他的大O测量方法，如立方、指数和平方根，但它们并不常见。大O符号被描述为O(<类型>)，其中<类型>是度量。快速排序算法可以描述为O (N * log(N))。
请注意，所有这些都没有考虑最佳、平均和最坏的情况。每个都有自己的大O符号。还要注意，这是一个非常简单的解释。大O是最常见的，但它也更复杂。还有其他的符号，比如大的，小的o和大的。在算法分析课程之外，你可能不会遇到它们。；）
其他回答
这是一篇很好的文章:算法的时间复杂度
下面的答案是从上面复制的(以防优秀的链接崩溃)
计算时间复杂度最常用的度量是大O符号。这样就去掉了所有的常数因子，这样当N趋于无穷时，运行时间就可以相对于N进行估计。一般来说，你可以这样想:
statement;
是恒定的。语句的运行时间不会随着N的变化而改变。
for ( i = 0; i < N; i++ )
statement;
是线性的。循环的运行时间与N成正比，当N加倍时，运行时间也加倍。
for ( i = 0; i < N; i++ ) {
for ( j = 0; j < N; j++ )
statement;
}
是二次。两个循环的运行时间与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;
}
对数。算法的运行时间与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);
}
为N * log (N)。运行时间由N个对数循环(迭代或递归)组成，因此该算法是线性和对数的结合。
一般来说，对一维中的每一项都做某事是线性的，对二维中的每一项都做某事是二次的，将工作区域一分为二是对数的。还有其他的大O测量方法，如立方、指数和平方根，但它们并不常见。大O符号被描述为O(<类型>)，其中<类型>是度量。快速排序算法可以描述为O (N * log(N))。
请注意，所有这些都没有考虑最佳、平均和最坏的情况。每个都有自己的大O符号。还要注意，这是一个非常简单的解释。大O是最常见的，但它也更复杂。还有其他的符号，比如大的，小的o和大的。在算法分析课程之外，你可能不会遇到它们。；）
如何计算算法的时间复杂度
你把它将执行的机器指令数量作为输入大小的函数相加，然后将表达式简化为最大(当N非常大时)项，并可以包括任何简化的常数因子。
例如，让我们看看如何简化2N + 2个机器指令，将其描述为O(N)。
为什么要去掉两个2 ?
我们感兴趣的是N变大时算法的性能。
考虑2N和2这两项。
当N变大时，这两项的相对影响是什么?假设N是一百万。
第一项是200万，第二项只有2。
因此，对于大N，我们只保留最大的项。
现在我们从2N + 2到2N。
传统上，我们只对常数因素下的性能感兴趣。
这意味着当N很大时，我们并不关心性能差异是否有常数倍数。2N的单位一开始就没有明确定义。所以我们可以乘或除一个常数因子得到最简单的表达式。
所以2N变成了N。
时间复杂度示例
1 -基本操作(算术，比较，访问数组元素，赋值):运行时间总是常量O(1)
例子:
read(x) // O(1)
a = 10; // O(1)
a = 1,000,000,000,000,000,000 // O(1)
2 - If then else语句:只从两个或多个可能的语句中获取最大运行时间。
例子:
age = read(x) // (1+1) = 2
if age < 17 then begin // 1
status = "Not allowed!"; // 1
end else begin
status = "Welcome! Please come in"; // 1
visitors = visitors + 1; // 1+1 = 2
end;
因此，上述伪代码的复杂度为T(n) = 2 + 1+ max(1,1 +2) = 6。因此，它的大oh仍然是常数T(n) = O(1)。
3 -循环(for, while, repeat):此语句的运行时间为循环次数乘以循环内的操作次数。
例子:
total = 0; // 1
for i = 1 to n do begin // (1+1)*n = 2n
total = total + i; // (1+1)*n = 2n
end;
writeln(total); // 1
它的复杂度是T(n) = 1+4n+1 = 4n+ 2。因此，T(n) = O(n)。
4 -嵌套循环(循环中循环):由于在主循环中至少有一个循环，这条语句的运行时间使用O(n^2)或O(n^3)。
例子:
for i = 1 to n do begin // (1+1)*n = 2n
for j = 1 to n do begin // (1+1)n*n = 2n^2
x = x + 1; // (1+1)n*n = 2n^2
print(x); // (n*n) = n^2
end;
end;
通用运行时间
在分析算法时，有一些常见的运行时间:
O(1) – Constant time Constant time means the running time is constant, it’s not affected by the input size. O(n) – Linear time When an algorithm accepts n input size, it would perform n operations as well. O(log n) – Logarithmic time Algorithm that has running time O(log n) is slight faster than O(n). Commonly, algorithm divides the problem into sub problems with the same size. Example: binary search algorithm, binary conversion algorithm. O(n log n) – Linearithmic time This running time is often found in "divide & conquer algorithms" which divide the problem into sub problems recursively and then merge them in n time. Example: Merge Sort algorithm. O(n2) – Quadratic time Look Bubble Sort algorithm! O(n3) – Cubic time It has the same principle with O(n2). O(2n) – Exponential time It is very slow as input get larger, if n = 1,000,000, T(n) would be 21,000,000. Brute Force algorithm has this running time. O(n!) – Factorial time The slowest!!! Example: Travelling salesman problem (TSP)
摘自这篇文章。它解释得很好，你应该读一读。
O(n)是大O符号，用于表示算法的时间复杂度。当你把一个算法的执行次数加起来时，你会得到一个像2N+2这样的结果。在这个表达式中，N是主导项(N的值增加或减少对表达式影响最大的项)。O(N)是时间复杂度N是主要项。
例子
For i = 1 to n;
j = 0;
while(j <= n);
j = j + 1;
这里内层循环的总执行次数为n+1，外层循环的总执行次数为n(n+1)/2，因此整个算法的总执行次数为n+1 + n(n+1/2) = (n2 + 3n)/2。 这里n²是主导项所以这个算法的时间复杂度是O(n2)
当你分析代码时，你必须一行一行地分析，计算每个操作/识别时间复杂度。最后，你必须把它加起来才能得到整体。
例如，你可以有一个线性复杂度的简单循环，但在同一个程序中，你可以有一个三次循环，它具有三次复杂度，所以你的程序将具有三次复杂度。函数的生长顺序在这里起作用。
让我们看看一个算法的时间复杂度有哪些可能，你可以看到我上面提到的增长顺序:
Constant time has an order of growth 1, for example: a = b + c. Logarithmic time has an order of growth log N. It usually occurs when you're dividing something in half (binary search, trees, and even loops), or multiplying something in same way. Linear. The order of growth is N, for example int p = 0; for (int i = 1; i < N; i++) p = p + 2; Linearithmic. The order of growth is n·log N. It usually occurs in divide-and-conquer algorithms. Cubic. The order of growth is N3. A classic example is a triple loop where you check all triplets: int x = 0; for (int i = 0; i < N; i++) for (int j = 0; j < N; j++) for (int k = 0; k < N; k++) x = x + 2 Exponential. The order of growth is 2N. It usually occurs when you do exhaustive search, for example, check subsets of some set.
