帅帅最棒滴 2021-09-18 13:57 采纳率: 100%
浏览 43
已结题

数据结构与算法求解答

求时间复杂度

  1. i=1;
    while(i<n)
    i=i*2

  2. for(i=0;i<n;i++)
    for(j=i;j<n;j++)
    b[i][j]=i*2

求解,为什么第一个为log2 n
第二个为什么为n2

  • 写回答

2条回答 默认 最新

  • 爱晚乏客游 2021-09-18 14:28
    关注

    1、i每次增加两倍,那么相当于运行x次之后需要满足i^x<n,i^(x+1)>n,那么x的大小就是log2 n
    2。第二个数双重for循环,每一重都是0-n,那么你去计算频次的话就是N^2

    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论
  • 码农C风 2021-09-18 14:45
    关注

    复杂度是看执行频度的量级,注意是量级,第一个是小于n、i每次增加一倍,执行了多少次呢 i*2^x =n 那么x不就是log2 n了
    第二个第一重是0-n,二重循环是i到n,那么执行次数是n+……1,高斯公式,(n+1)n/2、量级是n的平方

    评论
查看更多回答(1条)

报告相同问题?

问题事件

  • 系统已结题 9月27日
  • 已采纳回答 9月19日
  • 创建了问题 9月18日

悬赏问题

  • ¥15 定义过的变量报错未定义
  • ¥15 如何在EXCEL某单元格中查找是否存在另一列中的内容。
  • ¥50 非对称加密(相关搜索:密码学)
  • ¥15 关于非编程寻迹小车的分析
  • ¥15 java导出EXCEL这里已经执行成功了,但是流浪器没有下载
  • ¥15 帮我把代码改的能正常运行就行
  • ¥50 有限元修正、模型修正、最小二乘法,详细步骤
  • ¥15 用plc编写梯形程序
  • ¥15 关于#物联网#的问题:新大陆AIOT中,按照手册教程进行添加,设置完成后网关一直不上线,显示Never这是网络服务的信息
  • ¥15 这个要用一维热方程但是我不知道怎么运用这个公式