快排 加 一个for 时间复杂度是多少呢

Question

初学算法，不太懂这块的概念，比如一个函数

function fn(){
    //快排
    //for(i = 0; i < n; i++){}
}

像这样的话，这个时间复杂度怎么算呢，是O(nlogn+n)吗，还是时间复杂度就不能这么算
望各位不吝赐教

Answer 1

算大的那个 o(nlogn)

Answer 2

百度百科：

在计算时间复杂度的时候，先找出算法的基本操作，然后根据相应的各语句确定它的执行次数，再找出 T(n) 的同数量级（它的同数量级有以下：1，log2n，n，n log2n ，n的平方，n的三次方，2的n次方，n!），找出后，f(n) = 该数量级，若 T(n)/f(n) 求极限可得到一常数c，则时间复杂度T(n) = O(f(n))
例：算法：

for(i=1; i<=n; ++i)
{
    for(j=1; j<=n; ++j)
    {
        c[i][j] = 0;//该步骤属于基本操作执行次数：n的平方次
        for(k=1; k<=n; ++k)
            c[i][j] += a[i][k] * b[k][j];//该步骤属于基本操作执行次数：n的三次方次
    }
}

则有T(n)=n^3+n^2，根据上面括号里的同数量级，我们可以确定 n的三次方 为T（n）的同数量级
则有f(n)=n^3，然后根据 T(n)/f(n) 求极限可得到常数c
则该算法的时间复杂度：T(n) = O(n^3) 注：n^3即是n的3次方。

重点的地方帮你标粗了，你指的O(nlogn+n) 相当于这个示例中的T(n)=n^3+n^2，但是示例的时间复杂度是f(n)=n^3，因为当n极限大时，n^2相对于n^3忽略不计了，所以最终时间复杂度就是f(n)=n^3。换句话说，时间复杂度基本只有1，log2n，n，n log2n ，n的平方，n的三次方，2的n次方，n!这几种情况，不会存在你这个nlogn+n这种情况

Answer 3

初学者可以简单地理解为一个for循环就是一个O(n)，for循环嵌套一个循环就是for(n^2)，不嵌套的两(多)个for循环依旧是O(n)。

Answer 4

在复杂度的计算里，相加的关系是不会引起复杂度数量级变化的，只有次方或者log才会引起数量级的变化
例如：

O(N+N) = O(2N) = O(N)
O(N^2+N) = O(N^2)

这应该是根据数学里的无穷大的相关思想来的，希望可以帮助到你。