循环的几个例子。

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

从这里开始-算法的时间复杂度介绍

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进行估计。一般来说，你可以这样想:

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和大的。在算法分析课程之外，你可能不会遇到它们。；）

时间复杂度示例

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)