我已经通过谷歌和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 !)等等。
当前回答
如何计算算法的时间复杂度
你把它将执行的机器指令数量作为输入大小的函数相加，然后将表达式简化为最大(当N非常大时)项，并可以包括任何简化的常数因子。
例如，让我们看看如何简化2N + 2个机器指令，将其描述为O(N)。
为什么要去掉两个2 ?
我们感兴趣的是N变大时算法的性能。
考虑2N和2这两项。
当N变大时，这两项的相对影响是什么?假设N是一百万。
第一项是200万，第二项只有2。
因此，对于大N，我们只保留最大的项。
现在我们从2N + 2到2N。
传统上，我们只对常数因素下的性能感兴趣。
这意味着当N很大时，我们并不关心性能差异是否有常数倍数。2N的单位一开始就没有明确定义。所以我们可以乘或除一个常数因子得到最简单的表达式。
所以2N变成了N。
其他回答
如何计算算法的时间复杂度
你把它将执行的机器指令数量作为输入大小的函数相加，然后将表达式简化为最大(当N非常大时)项，并可以包括任何简化的常数因子。
例如，让我们看看如何简化2N + 2个机器指令，将其描述为O(N)。
为什么要去掉两个2 ?
我们感兴趣的是N变大时算法的性能。
考虑2N和2这两项。
当N变大时，这两项的相对影响是什么?假设N是一百万。
第一项是200万，第二项只有2。
因此，对于大N，我们只保留最大的项。
现在我们从2N + 2到2N。
传统上，我们只对常数因素下的性能感兴趣。
这意味着当N很大时，我们并不关心性能差异是否有常数倍数。2N的单位一开始就没有明确定义。所以我们可以乘或除一个常数因子得到最简单的表达式。
所以2N变成了N。
其他答案集中在大o符号和实际例子上。我想从理论的角度来回答这个问题。下面的解释必然缺乏细节;Michael Sipser的《计算理论导论》是学习计算复杂性理论的一个很好的来源。
图灵机
研究计算问题的最广泛的模型是图灵机。图灵机有一个一维的纸带，上面有符号，用作存储设备。它有一个磁带头，用来从磁带中读写。它有一个决定机器行为的转换表，这是一个在机器创建时决定的固定硬件组件。图灵机在离散时间步长下工作，如下所示:
它能读出胶带下面的符号。 根据符号及其内部状态(只能取有限个值)的不同，它从转换表中读取三个值s、σ和X，其中s是内部状态，σ是符号，X是左或右。
它的内部状态变成了s。
它将读取的符号更改为σ。
它将磁带头按照X的方向移动一步。
图灵机是强大的计算模型。它们能做你的数字计算机能做的一切。它们是在现代数字计算机出现之前由理论计算机科学之父和数学家艾伦·图灵提出的。
时间复杂度
It is hard to define the time complexity of a single problem like "Does white have a winning strategy in chess?" because there is a machine which runs for a single step giving the correct answer: Either the machine which says directly 'No' or directly 'Yes'. To make it work we instead define the time complexity of a family of problems L each of which has a size, usually the length of the problem description. Then we take a Turing machine M which correctly solves every problem in that family. When M is given a problem of this family of size n, it solves it in finitely many steps. Let us call f(n) the longest possible time it takes M to solve problems of size n. Then we say that the time complexity of L is O(f(n)), which means that there is a Turing machine which will solve an instance of it of size n in at most C.f(n) time where C is a constant independent of n.
它不是依赖于机器吗?数字计算机能做得更快吗?
Yes! Some problems can be solved faster by other models of computation, for example two tape Turing machines solve some problems faster than those with a single tape. This is why theoreticians prefer to use robust complexity classes such as NL, P, NP, PSPACE, EXPTIME, etc. For example, P is the class of decision problems whose time complexity is O(p(n)) where p is a polynomial. The class P do not change even if you add ten thousand tapes to your Turing machine, or use other types of theoretical models such as random access machines.
理论与实践的差异
通常假设整数加法的时间复杂度为O(1)。这种假设在实践中是有意义的，因为计算机使用固定数量的位来存储许多应用程序的数字。理论上没有理由假设这样的事情，所以加法的时间复杂度是O(k)其中k是表示整数所需的比特数。
寻找一类问题的时间复杂度
显示问题时间复杂度的最直接方法是构造一个图灵机，它能在O(f(n))时间内解决问题。为复杂问题创建图灵机并非易事;人们需要熟悉它们。图灵机的转换表很少给出，它是高层次的描述。随着人们对机器的熟悉，就更容易看到机器需要多长时间才能停下来。
说明一个问题不是O(f(n))时间复杂度是另一回事……尽管有一些像时间层次定理这样的结果，但这里还有很多悬而未决的问题。例如，NP中的问题是否在P中，即是否可在多项式时间内解决，是数学千年大奖中的七个问题之一，解决者将获得100万美元的奖励。
当你分析代码时，你必须一行一行地分析，计算每个操作/识别时间复杂度。最后，你必须把它加起来才能得到整体。
例如，你可以有一个线性复杂度的简单循环，但在同一个程序中，你可以有一个三次循环，它具有三次复杂度，所以你的程序将具有三次复杂度。函数的生长顺序在这里起作用。
让我们看看一个算法的时间复杂度有哪些可能，你可以看到我上面提到的增长顺序:
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.
对于有数学头脑的人来说:主定理是研究复杂性时另一个有用的东西。
简单地说，时间复杂度是一种总结算法的操作数量或运行时间如何随着输入大小的增加而增长的方式。
就像生活中的大多数事情一样，鸡尾酒会可以帮助我们理解。
O(N)
当你到达派对时，你必须和每个人握手(每件事都要做一次操作)。随着出席人数N的增加，你与每个人握手的时间/工作时间也随着O(N)的增加而增加。
为什么是O(N)而不是cN?
与人握手所用的时间各不相同。你可以把它平均出来，用常数c来表示。但这里的基本操作——和每个人握手——总是与O(N)成正比，不管c是多少。当我们讨论是否应该参加鸡尾酒会时，我们通常更感兴趣的是我们必须与每个人见面，而不是那些会面的细节。
O (N ^ 2)
鸡尾酒会的主人想让你玩一个愚蠢的游戏，让每个人都遇见其他人。因此，你必须会见N-1个人，因为下一个人已经见过你，他们必须会见N-2个人，以此类推。这个级数的和是x^2/2+x/2。随着参与者人数的增加，x^2项很快就变大了，所以我们就把其他的都丢掉了。
O (N ^ 3)
你必须和其他人见面，在每次会议期间，你必须谈论房间里的其他人。
O(1)
主持人想宣布一件事。他们敲着酒杯大声说话。每个人都能听到。事实证明，不管有多少参与者，这个操作总是花费相同的时间。
O（对数 N）
主人已经把每个人按字母顺序排列在桌子上。丹在哪里?你推断他一定在亚当和曼迪之间(当然不是在曼迪和扎克之间!)。鉴于此，他在乔治和曼迪之间吗?不。他肯定在亚当和弗雷德之间，在辛迪和弗雷德之间。等等……我们可以有效地定位丹，只需要看一半的集合，然后再看一半的集合。最终，我们观察O(log_2 N)个个体。
O(nlogn)
您可以使用上面的算法找到在桌子旁的位置。如果有很多人来到这张桌子前，一次一个，所有人都这样做，这将花费O(nlog N)个时间。结果证明，这是对必须进行比较的项目集合进行排序所需的时间。
最好/最坏情况
你到达了派对，需要找到伊尼戈——需要多长时间?这取决于你什么时候到。如果每个人都在周围转悠，你就遇到了最坏的情况:将花费O(N)时间。然而，如果每个人都坐在桌子旁，只需要O(log N)时间。或者你可以利用主持人的酒杯呐喊能力，这样只需要O(1)时间。
假设主机不可用，我们可以说inigo查找算法的下界为O(log N)，上界为O(N)，这取决于您到达时聚会的状态。
空间与通信
同样的想法也可以应用于理解算法如何使用空间或通信。
Knuth写了一篇关于前者的好论文，题为《歌曲的复杂性》。
定理2:存在复杂度为O(1)的任意长歌曲。 证据:(由于凯西和阳光乐队)。考虑一下Sk用(15)定义的歌曲，但是用
V_k = 'That's the way,' U 'I like it, ' U
U = 'uh huh,' 'uh huh'
对于所有的k。
