帅帅最棒滴
2021-09-18 13:57
采纳率: 100%
浏览 31

数据结构与算法求解答

求时间复杂度

  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的平方

    打赏 评论

相关推荐 更多相似问题