数据结构——计算算法时间复杂度

算法的时间复杂度，也就是算法的时间量度，记作：T(n) = O(f(n))。它表示随时间规模n的增大，算法执行时间的增长率和f(n)的增长率相同，称作算法的渐进时间复杂度，简称为时间复杂度。其中f(n)是问题规模b的某个函数。

这样用大写O()来体现算法的时间复杂度的计法，称为大O计法

推导大O阶：

1. 用常数1取代运行时间中的所有加法常数
2. 在修改后的运行次数函数中，之保留最高阶数
3. 如果最高阶存在且不是1，则去除与这个项相乘的常数

常数阶

int sum =0, n = 100;
sum = (1+n)*n/2;
cout<< sum;

这个算法的运行次数是f(n) = 3,根据推导大O阶的方法，第一步就是把常数3改为1保留最高阶时发现没有最高阶，所以算法复杂度是O(1)

线性阶

int sum = 0;
for(int i = 0; i< n ; i++)
{
    sum = sum + i;
}
cout<<sum;

因为循环体中的代码要执行n次，所以时间复杂度是O(n)

对数阶

int count = 1;
while(count < n){
    count = cont * 2;
}

由于每次count*2之后，就距离n更近了一分，也就是说有多少个2相乘后大于n，则会退出循环。由，所以这个循环的时间复杂度是

平方阶

例如循环嵌套，时间复杂度为

int i,j;
for(i = 0;i<n;i++){
    for(j = i; j <n; j ++)
    {
        ...
    }
}

总执行次数为：

推导大O阶：只保留最高项 因此保留,去除项相乘的常数，也就是去除1/2，最终时间复杂度为

看以下相对复杂的语句：

n ++ ;              //执行次数为1
f(n);                // 执行次数为n
for(int i = 0;i < n; i++){
    f(n);            // 执行次数为n2
}
for(int i = 0;i < n; i++){
    for(int j = i; j < n ; j ++)
    {
        
    }
}

它的执行次数为：，根据推导大O阶的方法，最终代码的时间复杂度也是