n,L = map(int, input().split(' ')) l = list(map(int, input().split(' '))) l.sort() sum=int(0) i=int(0) cnt=int(0) for i in range(n): if(sum<=L): sum+=l[i] cnt+=1 if(sum>L): sum-=l[i] cnt-=1 print(cnt) 时间复杂度分析
时间: 2023-06-27 11:05:32 浏览: 88
试写一时间复杂度为n的算法,并按要求改造表L
这段代码的时间复杂度为O(nlogn),其中n为输入的长度。
原因是,在第4行中,对输入的列表进行了一次排序操作,时间复杂度为O(nlogn)。之后,通过for循环遍历列表,每次判断sum是否小于等于L,如果是,则将当前数字加入sum,并将cnt加1;如果不是,则从sum中减去当前数字,并将cnt减1。由于for循环遍历了整个列表,因此时间复杂度为O(n)。因此,总的时间复杂度为O(nlogn+n),即O(nlogn)。
阅读全文