下面程序段的时间复杂度为() let i = 1; whil

[单选题]

下面程序段的时间复杂度为()

let i = 1;

while(i<=n)

i = i*3

```
O(n)
```
```
O(3n)
```
```
O()
```
```
O()
```

查看答案及解析

一笑而过2222

这个程序段的时间复杂度可以通过分析循环的次数来确定。程序中有一个 while 循环，每次循环都会将 i 的值乘以 3。我们可以观察到 i 的变化如下： 1. 初始值：i = 1 2. 第一次循环后：i = 1 \times 3 = 3 3. 第二次循环后：i = 3 \times 3 = 9 4. 以此类推，第 k 次循环后：i = 3^k 循环将一直进行，直到 i 大于 n。我们需要找到满足 3^k \leq n 的最大的 k 值，然后 k 就是循环的次数。对不等式 3^k \leq n 取对数，得到 k \log_3(3) \leq \log_3(n)，简化后得到 k \leq \log_3(n)。因为 k 是整数，我们需要取 k 的上界，即 k = \lceil \log_3(n) \rceil，其中 \lceil \cdot \rceil 表示向上取整。因此，循环的次数是 O(\log_3(n)

发表于 2024-07-03 09:42:12 回复(0)