循环的几个例子。

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。

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

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

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

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)