第21课 算法优化

学习要点

（1）掌握算法以及算法性能、算法效率的概念。

（2）理解算法的时间复杂度与空间复杂度。

对标内容

理解算法以及算法性能、算法效率的概念，初步了解算法优化效率的方法。

应用while语句解决实际问题

for、while循环复习

求1+3+5+7+9+11+13的和，用for循环和while循环实现的程序分别如下所示。

#for循环
sum=0
for i in range(1,14,2):
    sum+=i
print(sum)

#while循环
sum=0
n=1
while n<=13:
    sum=sum+n
    n=n+2
print(sum)

说明：while循环的语法结构如下所示。

初时状态设置
while 条件
    循环体（每次都重复进行的操作，其中必须包括能改变循环控制变量的操作）

例题 1

有30名男生和20名女生，平均分成若干个小组参加户外CS活动，要使每个小组内的男生人数相同，女姓人数也相同，可以分成几个小组？有几种分法？

代码1

nan = 30
nv = 20
i = 2
n = 0
while i <= 30:
    if nan % i == 0 and nv % i == 0 :
        print( str(i) + "个小组")
        n = n + 1
    i = i + 1
print( str(n) + "种分法")

优化后的代码2

nan = 30
nv = 20
i = 2
n = 0
while i <= 20:
    if nan % i == 0 and nv % i == 0 :
        print( str(i) + "个小组")
        n = n + 1
    i = i + 1
print( str(n) + "种分法")

例题 ２

从６月1日起，小明的妈妈要每工作3天休息1天，爸爸要工作4天休息1天，请你帮忙计算一下小明一家在6月可以选择哪几天共同休息的日子去奶奶家玩。 代码 1

t = 1
n=0
s = ""
while t <= 30:
    if t % 4 == 0 and t % 5 == 0:
        s = s + "6月" + str(t) + "日    "
        n=n+1
    t = t + 1
print( s,n)

优化后的代码２

t = 4
n=0
s = ""
while t <= 30:
    if t % 4 == 0 and t % 5 == 0:
        s = s + "6月" + str(t) + "日    "
        n=n+1
    t = t + 4
print( s,n)

小结：优化while程序，可以考虑优化循环条件、循环控制变量。

提炼：上述两个问题体现了枚举算法的思想。

易错点

（1）枚举范围应尽可能小，但又不能遗漏。 （2）循环的步长应尽可能大。

模拟考题

考题1 单选题

用枚举算法求解“找出所有满足各位数字之和等于７的三位数”时，在下列数值范围内，算法执行效率最高的是（）。

A. 0~999 B. 100~999 C. 100~700 A. 106~700

答案：D

解析∶枚举的范围应尽可能小但又不遗漏。

考题2 判断题

描述算法可以有不同的方式，可用自然语言，也可以用流程图等。（ ）

答案：正确

时间复杂度与空间复杂度

知识点讲解

时间复杂度的概念

一般情况下，算法中基本操作重复执行的次数是问题规模n的某个函数f(n)，算法的时间度量记作T(n)=O((n))，它表示随问题规模n的增大，算法执行时间的增长率和f(n)的增长关系，称作算法的渐进时间复杂度，简称时间复杂度。

时间复杂度T(n)按数量级递增顺序为∶

计算时间复杂度的步骤

（1）找到执行次数最多的语句。

（2）衡量执行语句的数量级。

（3）用O()表示结果。

（4）然后用常数1取代运行时间中的所有加法常数。

（5）在修改后的运行次数函数中，只保留最高阶项。

（6）如果最高阶项存在且不是1，那么就去除与这个项相乘的常数，比如3n^2^就取n^2^。最后即可得到想要的结果。

例题 1

print("111")
print("111")
print("111")
print("111")
print("111")
print("111")
print("111")
print("111")

打印８条语句，问这个程序的时间复杂度是多少？

O(8)？当然不是！按照时间复杂度的概念，“T(n)是关于问题规模为n的函数”，这里和问题规模有关系吗？没有关系，虽级为常数阶，时间复杂度O(1)。

例题 ２

sum=0
for i in range(100):
    sum+=i

量级为线性阶，时间复杂度为O(n)。

例题 ３

sum=0
for i in range(100):
    for j in range(100):
        sum+=j

量级为平方阶，外层i的循环执行一次，内层ｊ的循环就要执行100次，所以外层执行100次，总共需要执行100×100次。那么n次呢？就需要执行n×n次，即n^２^了，所以时间复杂度为O(n^2^)。

例题 ４

sum=0
for i in range(100):
    for j in range(i,100):
        sum+=j

量级为平方阶，当i=1时执行n次，当i＝２时执行（n-1）次…...—直这样下去就可以构造一个等差数列：n , n-1 , n-2 , ... , 2 , 1。 根据等差数列的求和公式得：n+n(n-1)/2，整理一下就是n(n+1)/2，然后将其展开可以得到n^2^/2+n/2。

根据我们的步骤，保留最高次项，去掉相乘的常数就可以得到时间复杂度为O(n^2^)。

例题 5

i=1 
n=100 
while i<n:
    i=i*2

量级为对数阶，2^x^=n，所以时间复杂度为O(log~2~n)。

时间复杂度小结∶平均运行时间是期望的运行时间，最坏的运行时间是一种保证。我们提到的运行时间都是最坏的运行时间。

空间复杂度的概念

空间复杂度是指算法被编写成程序后，在计算机中运行时所需存储空间大小的度量，记作S(n)=O(f(n))，其中n为问题的规模或大小。

存储空间一般包括3个部分∶

（1）输入数据所占用的存储空间；

（2）指令、常数、变量所占用的存储空间

（3）辅助（存储）空间。

算法的空间复杂度一般指的是辅助空间。

一维数组a[n]的空间复杂度为O(n)。

二维数组a[n][m]的空间复杂度为O(n*m)。

易错点

（1）熟记时间复杂度与空间复杂度的计算实例。

（2）理解时间复杂度与空间复杂度的概念。

模拟考题

考题1 单选题

在使用Python编写程序时，提到的“时间复杂度”中的“时间”一般是指( )。

A.算法执行过程中所需要的基本运算时间

B.算法执行过程中编译代码所花时间

C. 算法执行过程中所需要的基本运算次数

D.程序代码的复杂程度

答案：C

解析∶“时间复杂度”中的“时间”是指算法执行过程中所需要的基本运算次数。

考题2 判断题

如果执行算法所需的临时空间不会随变量的变化而变化，那么该算法的空间复杂度为一个常量。（ ）

答案：正确

解析∶如果执行算法所需的临时空间不会随变量的变化而变化，其算法的空间复杂度为常量O(1)。

算法优化单元测试题

模拟考题

一、单选题(共5题，每题10分，共50分)

1、下面的程序输出1~100之间能被7整除但不能同时被5整除的所有整数。

k=1
while k<101:
   if k%7==0 and k%5 !=0:
       print(k)
   k += 1

根据下面哪个选项的方法优化后，程序的运行效率最高？（ ）

A. 将k=1改为k=7

B. 将k += 1改为k += 5

C. 将k += 1改为k += 7

D. 将k=1改为k=7，同时将k += 1改为k += 7

2、关于评价算法的优劣，以下说法正确的是？（　）

A. 只要考虑是否得出正确答案。

B. 只要考虑算法的执行时间。

C. 只要考虑算法所占用的空间。

D. 从算法执行时间和需占用的空间两方面考虑。

3、下列不是评判一个算法优劣的标准是？（ ）

A. 时间复杂度

B. 空间复杂度

C. 难易度

D. 健壮性

4、李宇同学利用Python语言编写了一段“根据出生年月判断生肖属相”的程序，调试运行时，程序没有报错且顺利运行，但未能正确输出对应属相，造成这个结果的原因可能是？（ ）

A. 程序语句语法错误

B. 时间复杂度太高

C. 求解算法逻辑错误

D. Python环境配置不对

5、下列排序算法中，时间复杂度最小的是？（　）

A. 插入排序

B. 冒泡排序

C. 快速排序

D. 选择排序

二、判断题(共5题，每题10分，共50分)

6、算法的时间复杂度与空间复杂度没有必然关系。

​ 正确 错误

7、通常问题的规模越大算法执行的时间就越长，算法执行时间的增长率和问题规模的增长关系，称为空间复杂度。

​ 正确 错误

8、算法复杂度分析的目的是分析算法的效率，以求改进。

​ 正确 错误

9、primenumber(number)函数是判断一个数是否是素数的函数，将函数的循环条件

​ “for i in range(2,number)”更改为“for i in range(2,number//2)”

​ 能够降低primenumber(number)函数的时间复杂度。

def primenumber(number):
    if number < 2:    
        print(number,"不是素数！")    
    else:    
        for i in range(2,number):    
            if number % i == 0:    
                print(number,"不是素数！")    
                break    
        else:   
            print(number,"是素数!")

​ 正确 错误

10、计算下面这段程序的时间复杂度为平方阶：O(n^2)。（ ）

sum1=0
for i in range(101):
    sum1+=i

​ 正确 错误

答案

一、单选题 1、D 2、D

3、C

试题解析：评价算法的优劣是：时间复杂度，空间复杂度，健壮性，正确性，可读性。因此选C。

4、C

试题解析：程序能正常运行，排除了其他三个可能。

5、C

试题解析：快速排序时间复杂度是O(nlogn)，其他都是O(n*n)

二、判断题

6、T 7、F 8、T 9、F

10、F

试题解析：时间复杂度为线性阶，计O(n)。