时间复杂度（Time Complexity）不是度量具体一个算法具体的耗时是多少。时间复杂度通常用大O表示法，它不包括这个函数的低阶项和首项系数，可以表示为T[n]=O(f(n))，称函数T(n)以f(n)为界或者称T(n)受限于f(n)。 如果一个问题的规模是n，解这一问题的某一算法所需要的时间为T(n)。大O表示法给出的是一个上界，而非一个上确界。

大O符号是由德国数论学家保罗·巴赫曼（Paul Bachmann）在其1892年的著作《解析数论》（Analytische Zahlentheorie）首先引入的。

常见的时间复杂度量级有：

• 常数阶O(1)
• 对数阶O(logN)
• 线性阶O(n)
• 线性对数阶O(nlogN)
• 平方阶O(n2)
• 立方阶O(n3)
• K次方阶O(n^k)
• 指数阶(2^n)

常数阶O(1)

// 无论代码有多少行，只要没有循环等结构，那么时间复杂度就是O(1)。
int x = 13;
x = x + 1;
x = x + 1;
x = x + 1;
x = x + 1;
x = x + 1;
x = x + 1;
x = x + 1;
x = x + 1;
x = x + 1;

对数阶O(logN)

public void main()
{
    int i = 1;
    while(i<n)
    {
        // i在每个循环都将乘以2，假设循环x次之后，i就大于n，循环退出，程序结束，那么2^x=n => x=log2(n)，所以时间复杂度为：O(logN)
        i = i * 2;
    }
}

线性阶O(n)

public void main()
{
    int i = 1;
    while(i<n)
    {
        // 执行循环x次后，程序退出，那么x=n => O(n)。
        // 如果i=i+2，时间复杂度同样是O(n)，因为2x=n => O(n/2) => O(n)，因为当n接近于无穷大的时候，常量可以忽略。
        i = i + 1;
    }
}

线性对数阶O(nlogN)

public void main()
{
    int i = 1;
    while(i<n)
    {
        for(int j=1;j)
            j = j*2;
    }
}

平方阶O(n2)

public void main()
{
    for(int i=1;i)
        for(int j=1;j)
            j = j+1;
    }
}

立方阶O(n3)

public void main()
{
    for(int i=1;i)
        for(int j=1;j)
            for(int k=1;k)
                k = k+1;
    }
}

K次方阶O(n^k)

与立方阶O(n3)类似，多层循环。

指数阶(2^n)

比如，旅行商问题（Travelling Salesman Problem，简称TSP）