我已经通过谷歌和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 !)等等。
当前回答
从这里开始-算法的时间复杂度介绍
1. 简介
在计算机科学中，算法的时间复杂度将算法运行所需的时间量化为表示输入的字符串长度的函数。
2. 大O符号
算法的时间复杂度通常用大O符号表示，其中不包括系数和低阶项。当以这种方式表示时，时间复杂度被称为渐近描述，即当输入大小趋于无穷大时。
例如，如果一个算法对所有大小为n的输入所需要的时间最多为5n3 + 3n，则渐近时间复杂度为O(n3)。稍后再详细介绍。
再举几个例子:
1 = O（n） n = O（n2） log（n） = O（n） 2 n + 1 = O（n）
3.O(1)常数时间:
不管输入大小如何，如果一个算法需要相同的时间，我们就说它在常数时间内运行。
例子:
数组:访问任意元素 固定大小的堆栈:push和pop方法 固定大小的队列:入队列和出队列方法
4. O(n)线性时间
如果一个算法的时间执行与输入大小成正比，即时间随着输入大小的增加而线性增长，则该算法被称为在线性时间内运行。
考虑下面的例子。下面我线性搜索一个元素，它的时间复杂度是O(n)。
int find = 66;
var numbers = new int[] { 33, 435, 36, 37, 43, 45, 66, 656, 2232 };
for (int i = 0; i < numbers.Length - 1; i++)
{
if(find == numbers[i])
{
return;
}
}
更多的例子:
数组:线性搜索，遍历，查找最小值等 ArrayList:包含方法 Queue:包含方法
5. O(log n)对数时间:
如果一个算法的执行时间与输入大小的对数成正比，则该算法在对数时间内运行。
示例:二分搜索
回想一下“二十个问题”游戏——任务是在一段时间内猜测一个隐藏数字的值。每次你猜的时候，都会被告知你猜的是太高还是太低。二十题游戏暗示了一种策略，使用你的猜测数字来减半间隔大小。这是一个被称为二分搜索的一般问题解决方法的例子。
6. O(n2)二次时间
如果一个算法的执行时间与输入大小的平方成正比，我们就说它在二次时间内运行。
例子:
冒泡排序 选择排序 插入排序
7. 一些有用的链接
大0误解 算法复杂度的确定 大O小抄
其他回答
时间复杂度示例
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)
摘自这篇文章。它解释得很好，你应该读一读。
对于有数学头脑的人来说:主定理是研究复杂性时另一个有用的东西。
当你分析代码时，你必须一行一行地分析，计算每个操作/识别时间复杂度。最后，你必须把它加起来才能得到整体。
例如，你可以有一个线性复杂度的简单循环，但在同一个程序中，你可以有一个三次循环，它具有三次复杂度，所以你的程序将具有三次复杂度。函数的生长顺序在这里起作用。
让我们看看一个算法的时间复杂度有哪些可能，你可以看到我上面提到的增长顺序:
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.
从这里开始-算法的时间复杂度介绍
1. 简介
在计算机科学中，算法的时间复杂度将算法运行所需的时间量化为表示输入的字符串长度的函数。
2. 大O符号
算法的时间复杂度通常用大O符号表示，其中不包括系数和低阶项。当以这种方式表示时，时间复杂度被称为渐近描述，即当输入大小趋于无穷大时。
例如，如果一个算法对所有大小为n的输入所需要的时间最多为5n3 + 3n，则渐近时间复杂度为O(n3)。稍后再详细介绍。
再举几个例子:
1 = O（n） n = O（n2） log（n） = O（n） 2 n + 1 = O（n）
3.O(1)常数时间:
不管输入大小如何，如果一个算法需要相同的时间，我们就说它在常数时间内运行。
例子:
数组:访问任意元素 固定大小的堆栈:push和pop方法 固定大小的队列:入队列和出队列方法
4. O(n)线性时间
如果一个算法的时间执行与输入大小成正比，即时间随着输入大小的增加而线性增长，则该算法被称为在线性时间内运行。
考虑下面的例子。下面我线性搜索一个元素，它的时间复杂度是O(n)。
int find = 66;
var numbers = new int[] { 33, 435, 36, 37, 43, 45, 66, 656, 2232 };
for (int i = 0; i < numbers.Length - 1; i++)
{
if(find == numbers[i])
{
return;
}
}
更多的例子:
数组:线性搜索，遍历，查找最小值等 ArrayList:包含方法 Queue:包含方法
5. O(log n)对数时间:
如果一个算法的执行时间与输入大小的对数成正比，则该算法在对数时间内运行。
示例:二分搜索
回想一下“二十个问题”游戏——任务是在一段时间内猜测一个隐藏数字的值。每次你猜的时候，都会被告知你猜的是太高还是太低。二十题游戏暗示了一种策略，使用你的猜测数字来减半间隔大小。这是一个被称为二分搜索的一般问题解决方法的例子。
6. O(n2)二次时间
如果一个算法的执行时间与输入大小的平方成正比，我们就说它在二次时间内运行。
例子:
冒泡排序 选择排序 插入排序
7. 一些有用的链接
大0误解 算法复杂度的确定 大O小抄
循环的几个例子。
O(n) time complexity of a loop is considered as O(n) if the loop variables is incremented / decremented by a constant amount. For example following functions have O(n) time complexity. // Here c is a positive integer constant for (int i = 1; i <= n; i += c) { // some O(1) expressions } for (int i = n; i > 0; i -= c) { // some O(1) expressions } O(nc) time complexity of nested loops is equal to the number of times the innermost statement is executed. For example, the following sample loops have O(n2) time complexity for (int i = 1; i <=n; i += c) { for (int j = 1; j <=n; j += c) { // some O(1) expressions } } for (int i = n; i > 0; i += c) { for (int j = i+1; j <=n; j += c) { // some O(1) expressions } For example, selection sort and insertion sort have O(n2) time complexity. O(log n) time complexity of a loop is considered as O(log n) if the loop variables is divided / multiplied by a constant amount. for (int i = 1; i <=n; i *= c) { // some O(1) expressions } for (int i = n; i > 0; i /= c) { // some O(1) expressions } For example, [binary search][3] has _O(log n)_ time complexity. O(log log n) time complexity of a loop is considered as O(log log n) if the loop variables is reduced / increased exponentially by a constant amount. // Here c is a constant greater than 1 for (int i = 2; i <=n; i = pow(i, c)) { // some O(1) expressions } //Here fun is sqrt or cuberoot or any other constant root for (int i = n; i > 0; i = fun(i)) { // some O(1) expressions }
时间复杂度分析的一个例子
int fun(int n)
{
for (int i = 1; i <= n; i++)
{
for (int j = 1; j < n; j += i)
{
// Some O(1) task
}
}
}
分析:
For i = 1, the inner loop is executed n times.
For i = 2, the inner loop is executed approximately n/2 times.
For i = 3, the inner loop is executed approximately n/3 times.
For i = 4, the inner loop is executed approximately n/4 times.
…………………………………………………….
For i = n, the inner loop is executed approximately n/n times.
因此上述算法的总时间复杂度为(n + n/2 + n/3 +…+ n/n)，即为n *(1/1 + 1/2 + 1/3 +…+ 1/n)
级数(1/1 + 1/2 + 1/3 +…+ 1/n)的重要之处在于大约是O(log n)，所以上面代码的时间复杂度是O(n·log n)。
引用:
1 2 3
