当前位置：首页 > news >正文

算法设计——最坏时间复杂度分析

news 2025/3/26 13:04:50

一、简介

二、大 O 表示法的定义

三、基本步骤

1.确定核心操作

2.分析执行次数

3.确定时间复杂度

四、例题

类型一：证明题

类型二：非递归算法的时间复杂度分析

类型三：递归算法的时间复杂度分析

一、简介

时间复杂度分为三种：

最坏情况时间复杂度：用大 O 表示法，记作 O(f(n))。它给出了算法运行时间的上界，即对于所有可能的输入规模 n，算法的运行时间都不会超过 O(f(n)) 的增长速度。例如，冒泡排序的最坏情况时间复杂度是 O(n^2)，表示随着输入规模 n 的增加，算法的运行时间增长速度不会超过 n^2 的增长速度。
最好情况时间复杂度：用大 Ω 表示法，记作 Ω(g(n))。它给出了算法运行时间的下界，即对于所有可能的输入规模 n，算法的运行时间至少是 Ω(g(n)) 的增长速度。例如，冒泡排序的最好情况时间复杂度是 Ω(n)，意味着在最好情况下，算法的运行时间增长速度不低于 n 的增长速度。
平均情况时间复杂度：用大 Θ 表示法，记作 Θ(h(n))。它表示算法在平均情况下的运行时间与 h(n) 的增长速度相同。例如，快速排序的平均情况时间复杂度是 Θ(nlogn)，说明在平均情况下，算法的运行时间与 nlogn 的增长速度一致。

我们通常使用的时间复杂度一般是“最坏情况的时间复杂度”，本篇文章主要介绍的就是用大 O 表示法对代码的时间复杂度进行分析。

二、大 O 表示法的定义

大表示法是一种用于描述函数渐近行为的数学符号，它忽略常数因子和低阶项，只保留最高阶项。对于一个函数，如果存在正常数和，使得当时，，则称。

三、基本步骤

1.确定核心操作

这里的“核心操作”指的是算法中最核心、执行次数最多且对运行时间影响最大的操作。举个例子，这里给出冒泡排序的C语言代码：

// 冒泡排序算法
void bubbleSort(int arr[], int n) {int i, j, temp;for (i = 0; i < n - 1; i++) {for (j = 0; j < n - i - 1; j++) {// 比较操作，这是基本操作之一if (arr[j] > arr[j + 1]) {// 交换操作，也是基本操作temp = arr[j];arr[j] = arr[j + 1];arr[j + 1] = temp;}}}
}

在上述冒泡排序代码中，if (arr[j] > arr[j + 1])这一行是比较操作，当条件满足时执行的交换操作（temp = arr[j]; arr[j] = arr[j + 1]; arr[j + 1] = temp;），这两个操作是冒泡排序中执行次数最多的基本操作，随着数组规模n的增大，它们的执行次数决定了算法的时间复杂度。

2.分析执行次数

由于我们要求的是“最坏的情况”，因此对于冒泡排序，最坏情况是初始序列完全逆序。

对于长度为 n 的数组，第一轮比较时，需要比较 (n - 1) 次，因为要把最大的元素 “浮” 到数组末尾；第二轮比较时，由于最大的元素已经在正确位置，所以只需要比较 (n - 2) 次；以此类推，直到最后一轮只需要比较 1 次。总的比较次数为:

3.确定时间复杂度

由大 O 表示法的定义可知，这里的就是常数因子，就是低阶项，随着 n 的不断增大，项的增长速度远远快于 n 项，常数因子对函数增长速度的影响也可以忽略不计，因此二者均可省略。最终只保留项，得到冒泡排序在最坏情况下的时间复杂度为 .

四、例题

类型一：证明题

例1. 求证：.

例2. 求证：.

类型二：非递归算法的时间复杂度分析

例3. 分析以下算法的时间复杂度。
void fun(int n)
{int s = 0, i, j, k;for(i=0; i<=n; i++)for(j=0; j<=i; j++)for(k=0; k<=j; k++)s++;
}

（1）分析核心操作：代码主体部分由三个循环嵌套组成，“核心操作”是 “s++”；

（2）确定执行次数：

（3）确定时间复杂度：去掉常数因子和低阶项可得，该算法的时间复杂度为.

例4. 给出以下算法的时间复杂度。
void func(int n)
{int i = 1, k = 100;while(i <= n){k++;i+=2;}
}

（1）分析核心操作：代码主体部分由 while 循环构成，“核心操作”为 “k++; i+=2;”;

（2）确定执行次数：设 while 循环语句执行的次数为 m，i 从 1 开始递增，最后取值为 1+2m，根据 while 循环结束条件 i <= n 可得 i = 1+2m <= n，即 .

（3）确定时间复杂度：去掉常数因子和低阶项可得，该算法的时间复杂度为.

类型三：递归算法的时间复杂度分析

例5. 求解汉诺塔问题的递归算法如下，分析其时间复杂度。

void Hanio(int n, char x, char y, char z)
{if(n==1){printf("将盘片%d从%c搬到%c\n",n,x,z);}else{Hanio(n-1, x, y, z);printf("将盘片%d从%c搬到%c\n",n,x,z);Hanio(n-1, y, x, z);}
}

这里给出汉诺塔问题的示意图（侵删）：

针对汉诺塔递归问题算法的代码，可做如下分析：

当汉诺塔总共只有一层时，只要将该层从 A 移到 C 就可以了，所有代码只要执行一次；当层数大于一时（假设层数为 n，即问题规模为 n 时），第一步需要先将除了最大的盘以外的所有盘从 A 移到 B，接着将最大的盘从 A 移到 C，此时还需要进行一步操作，就是将 B 上所有的盘回归到 A 上，这样问题规模就降为（n-1），即现在只需要将（n-1）个盘从 A 移到 C，如此递归，直到 A 盘上只剩一个盘，此时问题规模降为 1，由此问题可以得到解决。

设调用 Hanio(n, x, y, z) 的执行时间为 T(n)，由其执行过程得到以下求执行时间的递推关系：