双层for循环时间复杂度_2 常见的时间复杂度实例

3cbebad6cfb1d4c3f7e4ee6edadfd13b.png
系列文章参考资料为《大话数据结构》，源码为个人私有，未经允许不得转载

1.常数阶

参考下高斯的算法，时间复杂度为O(1)

int sum = 0,n = 100;        /* 执行一次 */
sum = (1 + n) * n / 2;      /* 执行一次 */
printf（"%d", sum）;          /* 执行一次 */

函数的运行次数函数f(n)=3
根据大0阶方法，第一步就是把3改为1，而且这个算法是没有最高阶的，所以这个算法的时间复杂度是O(1),也叫常数阶

2.线性阶

因为要执行n次，时间复杂度为O(n)

int i;
for（i = 0; i < n; i++）
{
    /* 时间复杂度为O(1)的程序步骤序列 */
}

3.对数阶

每次count乘2距离n就更近，也就是说有多少2相乘后会大于n，然后退出循环，2^x=n 得到x=log2n，时间复杂度为O(logn)

int count = 1;
while （count < n）
{
    count = count * 2;
    /* 时间复杂度为O(1)的程序步骤序列 */
}

4.平方阶

外层循环次数为n,内部也为n，时间复杂度为O(n^2)

int i,j;
for（i = 0; i < n; i++）
{
    for（j = 0; j < n; j++）                       
    {                                      
        /* 时间复杂度为O(1)的程序步骤序列 */
    }                                      
}

常见的时间复杂度总结

0df053cdb4c20f86e58cc64cbbae7e54.png

--------------------------------------------------------END-----------------------------------------------------------
电子书及源码点击下载