循环的几个例子。

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&nbsp;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

如何计算算法的时间复杂度

你把它将执行的机器指令数量作为输入大小的函数相加，然后将表达式简化为最大(当N非常大时)项，并可以包括任何简化的常数因子。

例如，让我们看看如何简化2N + 2个机器指令，将其描述为O(N)。

为什么要去掉两个2 ?

我们感兴趣的是N变大时算法的性能。

考虑2N和2这两项。

当N变大时，这两项的相对影响是什么?假设N是一百万。

第一项是200万，第二项只有2。

因此，对于大N，我们只保留最大的项。

现在我们从2N + 2到2N。

传统上，我们只对常数因素下的性能感兴趣。

这意味着当N很大时，我们并不关心性能差异是否有常数倍数。2N的单位一开始就没有明确定义。所以我们可以乘或除一个常数因子得到最简单的表达式。

所以2N变成了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小抄

简单地说，时间复杂度是一种总结算法的操作数量或运行时间如何随着输入大小的增加而增长的方式。

就像生活中的大多数事情一样，鸡尾酒会可以帮助我们理解。

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。

这是一篇很好的文章:算法的时间复杂度

下面的答案是从上面复制的(以防优秀的链接崩溃)

计算时间复杂度最常用的度量是大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) 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&nbsp;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