我已经通过谷歌和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)是大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)
其他回答
简单地说，时间复杂度是一种总结算法的操作数量或运行时间如何随着输入大小的增加而增长的方式。
就像生活中的大多数事情一样，鸡尾酒会可以帮助我们理解。
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。
如何计算算法的时间复杂度
你把它将执行的机器指令数量作为输入大小的函数相加，然后将表达式简化为最大(当N非常大时)项，并可以包括任何简化的常数因子。
例如，让我们看看如何简化2N + 2个机器指令，将其描述为O(N)。
为什么要去掉两个2 ?
我们感兴趣的是N变大时算法的性能。
考虑2N和2这两项。
当N变大时，这两项的相对影响是什么?假设N是一百万。
第一项是200万，第二项只有2。
因此，对于大N，我们只保留最大的项。
现在我们从2N + 2到2N。
传统上，我们只对常数因素下的性能感兴趣。
这意味着当N很大时，我们并不关心性能差异是否有常数倍数。2N的单位一开始就没有明确定义。所以我们可以乘或除一个常数因子得到最简单的表达式。
所以2N变成了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)是大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)
