详解时间复杂度计算公式(附例题细致讲解过程)-二、单层循环时间复杂度计算公式

时间：2024-04-16 20:21:52

 解题步骤

  1. 列出循环趟数t及每轮循环i的变化值
  2. 找到t与i的关系
  3. 确定循环停止条件
  4. 联立两式解方程
  5. 写结果

 例题分析

 例一：

i = n*n;
whlie(i != 1)
    i = i/2;

第一步：列出循环趟数t及每轮循环i的变化值：

t 0 1 2 3
i n^{2} \frac{n^2}{2} \frac{n^2}{4} \frac{n^2}{8}

第二步：找到t与i的关系：

 i=\frac{n^{2}}{2^{t}}

第三步：确定循环停止条件：

i = 1

第四步：联立第二步第三步两式解方程：

\frac{n^{2}}{2^{t}} = 1 \quad\quad n^2 = 2^t \quad\quad t = \log_2n^2

t = \log_2n^2 = 2\log_2n

所以得到时间复杂度为：

T = O(\log_2n)

例二:

x = 0；
while (n>=(x+1)*(x+1))
    x = x+1;

第一步：列出循环趟数t及每轮循环x的变化值：

t 0 1 2 3 4
x 0 1 2 3 4

第二步：找到t与x的关系：

 t = x

第三步：确定循环停止条件：

n = (x+1)^2

第四步：联立第二步第三步两式解方程：

(t +1)^2 = n

t = \sqrt[]{n}-1

所以得到时间复杂度为：

T=O(\sqrt[]{n})

 例三:

int i = 1;
while (i<=n)
    i = i *2

第一步：列出循环趟数t及每轮循环i的变化值：

t 0 1 2 3 4
i 0 1 2 3 4

第二步：找到t与x的关系：

 i = 2^t

第三步：确定循环停止条件：

i = n

第四步：联立第二步第三步两式解方程：

2^t = n

t = \log_2n

所以得到时间复杂度为：

T = O(\log_2n)

 例四:

int i = 0;
while (i*i*i<=n)
    i ++;

第一步：列出循环趟数t及每轮循环i的变化值：

t 0 1 2 3 4
i 0 1 2 3 4

第二步：找到t与x的关系：

 i=t

第三步：确定循环停止条件：

i^3 = t

第四步：联立第二步第三步两式解方程：

t^3 = n

t = \sqrt[3]{n}

所以得到时间复杂度为：

T=O( \sqrt[3]{n})

 例五:

y = 0;
while (y+1)*(y+1) <= n
    y = y+1;

第一步：列出循环趟数t及每轮循环y的变化值：

t 0 1 2 3 4
y 0 1 2 3 4

第二步：找到t与x的关系：

 t = y

第三步：确定循环停止条件：

(y+1)^2= n

第四步：联立第二步第三步两式解方程：

(t +1)^2 = n

t = \sqrt[]{n}-1

所以得到时间复杂度为：

T=O(\sqrt[]{n})

相关文章