计算此函数的复杂性

作者: 张三岁
发布时间: 2025-04-07 04:12:51 (4天前)
转自：

这是功能：

void f（int n）
{
for（int i = 0; i＆lt; n; ++ i）
for（int j = 0; j＆lt; i; ++ j）
for（int k = i * j; k＆gt; 0; k / = 2）
的printf（ “〜”）;
}
在我看来，计算时间……

2 条回复

0#
回复此人
google你他吗 | 2019-08-31 10-32
复杂性是
O(NNLOG_2(N^2))
。

第一个和第二个循环都有
O(N)
和最后一个循环
k
具有对数增长。
```
    
      LOG_2(N^2) = 2LOG_2(N) and
O(NM)=O(N)*O(M).
O(constant)=1.
</code>
  
```
因此，对于最后一个循环的增长，您也可以编写 O(LOG_2(N^2))=O(LOG(N)) 。
编辑

登录后才能参与评论