数据结构实验:设计算法并讨论其时间复杂度(Python实现)
实验目的
通过设计算法直观感知其时间复杂度,从而进一步理解算法的时间复杂度的概念,并能够计算出对应的时间复杂度。
实验内容
编写程序,在其中设计多个操作(包括无循环、单重循环和双重循环),体会算法的时间复杂度这一概念。通过以下步骤完成本实验。
1.实现无循环的方法
(1)简单地编写一个输出自己姓名和学号的语句。
(2)计算该方法的时间复杂度。
2.实现单重循环的方法
(1)利用单重循环求解正整数 1~n 的和。
(2)计算该方法的时间复杂度。
3.实现双重循环的方法
(1)利用双重循环输出九九乘法表。
(2)计算该方法的时间复杂度。
实验代码
class LoopCom(object):
################################
#实现无循环的方法
################################
def NoLoop(self):
name="张三"
id="20230113"
print("\n1.实现无循环的方法")
print("(1)简单地编写一个输出自己姓名和学号的语句。")
print(" 姓名为{0:},学号为{1:}".format(name,id))
print("(2)该算法的时间复杂度为O(1)。")
################################
#实现单重循环的方法
################################
def OneLoop(self):
sum=0
n=10
for i in range(1,n+1):
sum=sum+i
print("\n2.实现单重循环的方法")
print("(1)利用单循环求解正整数1~10的和。")
print(" 1-10的和为{0:}".format(sum))
print("(2)该算法的时间复杂度为O(n)。")
################################
#实现双重循环的方法
################################
def DoubleLoop(self):
print("\n3.实现双重循环的方法")
print("(1)利用双重循环输出九九乘法表。")
for i in range(1,10):
for j in range(1,i+1):
print("{0:}*{1:}={2:} ".format(i,j,i*j),end="")
print()
print("(2)该算法的时间复杂度为O(n^2)。")
################################
#输出函数
################################
def PrintOut(self):
self.NoLoop()
self.OneLoop()
self.DoubleLoop()
if __name__ == '__main__':
LC = LoopCom()
LC.PrintOut()
实验结果
1.实现无循环的方法
(1)简单地编写一个输出自己姓名和学号的语句。
姓名为张三,学号为20230113
(2)该算法的时间复杂度为O(1)。2.实现单重循环的方法
(1)利用单循环求解正整数1~10的和。
1-10的和为55
(2)该算法的时间复杂度为O(n)。3.实现双重循环的方法
(1)利用双重循环输出九九乘法表。
1*1=1
2*1=2 2*2=4
3*1=3 3*2=6 3*3=9
4*1=4 4*2=8 4*3=12 4*4=16
5*1=5 5*2=10 5*3=15 5*4=20 5*5=25
6*1=6 6*2=12 6*3=18 6*4=24 6*5=30 6*6=36
7*1=7 7*2=14 7*3=21 7*4=28 7*5=35 7*6=42 7*7=49
8*1=8 8*2=16 8*3=24 8*4=32 8*5=40 8*6=48 8*7=56 8*8=64
9*1=9 9*2=18 9*3=27 9*4=36 9*5=45 9*6=54 9*7=63 9*8=72 9*9=81
(2)该算法的时间复杂度为O(n^2)。