在此处输入图像描述
伪代码你能帮我找出算法的复杂性吗,因为这些j<-2j;i<-i+1让我有点不知所措。
让我们首先考虑内部循环:
j = 1
while j<=n
O(1)
j = 2*j
此循环针对j = 1,2,4,8,...
和j<=n
的值运行。因此,该循环将具有对数时间复杂度,即O(log n)
。
现在考虑外环:
i = 2
while i<=n
O(1)
//inner loop
i = i+1
此循环针对i = 2,3,,4,...,n
的值运行
因此外环具有线性时间复杂度,即O(n)
。
所以总时间复杂度= O(n)*O(log n) = O(n*log n)