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)

对于有数学头脑的人来说:主定理是研究复杂性时另一个有用的东西。

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

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

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

为什么要去掉两个2 ?

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

考虑2N和2这两项。

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

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

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

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

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

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

所以2N变成了N。

当你分析代码时，你必须一行一行地分析，计算每个操作/识别时间复杂度。最后，你必须把它加起来才能得到整体。

例如，你可以有一个线性复杂度的简单循环，但在同一个程序中，你可以有一个三次循环，它具有三次复杂度，所以你的程序将具有三次复杂度。函数的生长顺序在这里起作用。

让我们看看一个算法的时间复杂度有哪些可能，你可以看到我上面提到的增长顺序:

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) 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)