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

Fireworks_qwq:
听完之后大概做的笔记，可以参考参考，但是不一定完全准确，我计算机考研数据结构，如果有同学也考，不妨可以交流交流[妙啊]

【回复】二层的练习二应该是（n-1）(n-2)/2，是内层循环次数相加的和，等差数列[微笑]
【回复】两层循环练习二 j<i 应该是乘以n-1吧
【回复】请问双层循环的练习1的第四步nlog2n是哪来的呀
墨鱼仔7:
麻烦问一下up主，多层循环的时候如果把i++换成类似i*=2的形式应该怎么做呢，很好奇，虚心求教

【回复】回复 @夏喵喵喵喵喵 :22年真题
【回复】把循环次数设出来t次，把x随t增加的规律找出来（最好手推几轮 ，然后带入循环终止条件解出来n和t的关系
【回复】回复 @听泰勒斯能获得快乐吗 :那不是两层的吗，我没看以为真有这种题找了一下午[大哭][大哭][大哭]
LILILikeyou啊:
up的方法非常有限，只适用于结束循环条件时的判断含有“=”的情况，如果结束循环的条件中只含有一个大于或者小于就用不了了

【回复】可以用的。你要判断复杂度就不用纠结它具体小于等于还是只有小于。复杂度只研究量级的问题
【回复】也不是的吧，看你怎么理解循环结束的条件，i＜n可以看成结束循环是i＝n
【回复】比如小于n就直接那就是n-1，我刚看了方法把王道的时间复杂度题全过了一边，这套方法足够做所有题了
羊羊是朵云:
太牛了我终于懂了谢谢up[给心心][给心心][给心心][给心心]

【回复】没币了明天给你补一个[抱拳]
鱼鱼鱼块块块块:
想知道多层循环的练习题怎么做。。。不太会欸

学技术找一起:
课代表来噜！ 数据结构——时间复杂度计算??? 数据结构： 一层循环 例子 两层循环 一、一层循环 解题思路 二、例子 例子 答案 三...

Kkyyygg:
请问有大哥讲解一下这道题嘛[酸了][大哭] int func(int n){ int i = 0,sum = 0; while(sum < n) sum += ++i; return i; }

【回复】这不就是17年408真题嘛[大笑] 第1步、列出循环趟数t及每轮循环中sum的变化值（这道题起决定作用的变量是sum不是i） t： 0，1，2，3，4，5，...... sum：0，1，3，6，10，15，......，n 第2步、找到t与sum的关系 即sum=t(t+1)/2 第3步、确定循环停止条件 即sum=n 第4步、联立两式，解方程 即n=t(t+1)/2，然后解t 第5步、写结果 得答案 T=O(n^(1/2))
【回复】哇哇哇我明白啦！感谢大佬这么详细的解释[给心心][给心心][给心心]好认真
【回复】回复 @荣仔_最靓的仔 : 会写第一步，但是这个第二步不好找关系，请问有啥技巧吗
一尾取树:
问下up主 这题应该怎么做 用up的方法没算出来

【回复】外层循环i从1\2\4~n，一共log2n次，内部每次循环1\2\4~n次，也就是内部循环是一个等比数列，公比为2，求前log2n次和，答案是O(n)
【回复】O(n)，第一层循环无论i是几，第二层循环就循环多少次，所以把所有i的取值相加一起
【回复】回复 @松岛菜菜蔡菜菜子 : 错了，应该是等比，不应该用等差算，最后应该是2^log2 n=n
半吱小松徐zz:
感谢up 啊阿啊b站讲的最好的 之前老是弄不清 听完up这节视频做王道课后习题做一个对一个 极力推荐 考试一般都考有两个for的 大家一定要弄懂[脱单doge]已三连

只想摆烂星人:
在csdn上也有看到类似的帖子 不知道是不是您写的 太棒啦！

【回复】谢谢，CSDN同名呦[脱单doge]
琉霂LM:
10：17 因为k的变化是k*=2， 即k的变化是1、2、4、8、...这样的规律， 也可以看作2的零次幂、2的一次幂、2的二次幂、2的三次幂...2的i次幂， 又因为k<=n， 即可得，2的i次幂=k=n， 变形得，i=以2为底n的对数 因此，求和为：n倍以2为底n的对数 即t=o（nlog2^n）

【回复】1,2,4,8.....n等于出来的不是2的0次，1次，2次，3次吗，这样不是n=2的i-1次方，为什么是2的i次方
【回复】回复 @琉霂LM : 明白了谢谢！！
【回复】回复 @44456381515_bili :内层循环里面j是自增1，所以n是几就循环几次，外层循环一次内层循环n次。
飞翔的野鸡啊:
老师能用你的方法求解一下2022年的408统考题嘛 那个。。。不太会

【回复】回复 @飞翔的野鸡啊 : 外层i从1开始以i*2速度递增至n-1，共log₂(n-1)个数； 内层每轮循环j从0开始以j+1速度递增至i-1； 也就是说当i=1时，内层循环1次；当i=2时，内层循环2次；当i=4时，内层循环4次（j变化0→1→2→3）；依此类推…… 综上本题可转化为等比数列求和（项数为log₂n，首项为1，公比q为2） 立即推T=O(2^(log₂(n-1)))=O(n)
【回复】回复 @人从众paya : 外层i的变化是1，2，4，8，16，一直到n，总共有log2（n）项， 外层的个数是1，2，4，8，16.外层是一个公比为2的等比公式，项数是log2（n）项
白日幻想家克林:
想请教一下UP主 如果是这种两层的情况，怎么做呀，感觉做不出来，求解答[大哭][大哭] for（i=1;i<n;i*=2） for (j=0;j<i;j++) sun++

【回复】可以看看这个视频https://b23.tv/BV1U5411m7TX
【回复】回复 @雨溪ya :你的答案是对的
【回复】O(n)吗？[保卫萝卜_哭哭]
叶子-飘:
想问下大家这个怎么用up的方法做啊[大哭][大哭][大哭]

【回复】这道题选 B.O(n)，是递归类型的时间复杂度计算问题。 设该算法 fact(int n) 的时间复杂度表示为 T(n)， 语句 return 1; 的时间复杂度表示为 O(1)， 语句 return n*fact(n-1); 的时间复杂度表示为 T(n-1)+O(1)，其中，O(1) 表示基本操作——乘法的执行时间，T(n-1) 表示递归调用的时间复杂度。 通过递归求解（注意当 n<=1 时算法执行结束），则： T(n) = T(n-1) + O(1) = T(n-2) + O(1) + O(1) ...... = T(1) + O(1) + ...... + O(1) 【注：此处有 n-1 个 O(1)】 = O(1) + ...... + O(1) 【注：此处有 n 个 O(1)】 = O(1) * n = O(n) 综上，即 fact(int n) 的时间复杂度为 O(n)，故正确选项是 (B)。
【回复】回复 @荣仔_最靓的仔 :请问那道2*fact(2/n)+n怎么做呢
【回复】回复 @Z个好玩- :好哒，谢谢同学
无詪丶:
为啥三层循环最内层循环，从k=0到j-1对1求和的结果为j，这个咋算的

【回复】回复 @荣仔_最靓的仔 :最内层变量是k，为什么最内层变量求和变成了数的个数
【回复】回复 @荣仔_最靓的仔 : 请问为什么不是对k求和呢，而第二层是对j求和
【回复】回复 @珊珊珊珊诶 : 变量是谁就对谁求和。显然第二层变量是j，所以是对j求和；又因为最内层求和得j，所以第二层求和时用等差数列求和公式；同理可推最外层......