动力节点首页 全国咨询热线:400-8080-105

绑定手机号,登录
手机号

验证码

微信登录
手机号登录
手机号

验证码

30天自动登录
微信登录与注册
微信扫码登录与注册

扫码关注微信公众号完成登录与注册
手机号登录
首页 > 文章

算法时间复杂度

04-07 22:24 352浏览
举报 T字号
  • 大字
  • 中字
  • 小字

定义

在进行算法分析时,语句总的执行次数T(n)时关于问题规模n的函数,进而分析T(n)随n的变化情况并确定T(n)的数量级。算法的时间复杂度,也就是算法的时间度量,记作:T(n) = O(f(n))。它表示岁问题规模n的增大,称作算法的渐进时间复杂度,简称为时间复杂度。其中f(n)时问题规模n的某个函数。

说了半天就差不多要知道这个东西执行此时==时间

O()来提现算法时间复杂度的记法,称为大O记法

一般情况下,随着输入规模n的增大,T(n)增长最 慢 的算法为最优算法

推导大O阶方法

  • 用常数1取代运行时间中的所有加法常数
  • 在修改后的运行次数函数中,只保留最高阶项
  • 如果最高阶项数存在而且不是1,则去除与这个项相乘的常数
  • 得到的最后结果就是大O阶

常数阶:O(1)

线性阶:O(n)

一般含有非嵌套循环涉及线性阶,对应计算次数呈直线增长

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

平方阶:O(n^2)

如果n=100,外层执行一次,内层执行100次,所以程序执行了100^2次

int i, j, n = 100;
for (i = 0; i < n; i++)
{
    for (j = 0; j < n; j++)
    {
        printf("hello");
    }
}

但是如果存在

int i, j, n = 100;
for (i = 0; i < n; i++)
{
    for (j = i; j < n; j++)
    {
        printf("hello");
    }
}

他还是O(n^2)
对数阶:O(logn)

0人推荐
共同学习,写下你的评论
0条评论
代码小兵613
程序员代码小兵613

4篇文章贡献7032字

相关课程 更多>

作者相关文章更多>

推荐相关文章更多>

Java初学者学习方法

代码小兵64503-29 11:46

两道经典算法问题

代码小兵51603-29 13:18

Java中模拟高并发的方法

代码小兵87208-06 11:36

Java程序员必备的一些流程图

代码小兵64503-29 15:27

Java接口限流的实现方法

代码小兵57603-29 17:52

发评论

举报

0/150

取消