数据结构_day01_算法引入
120 浏览量
2020-12-21
16:39:57
上传
评论 1
收藏 198KB PDF 举报
数据结构数据结构_day01_算法引入算法引入
算法引入算法引入数据结构和算法Python版算法的提出补充:最坏时间复杂度:Python内置类型性能分析数据结构概念概念算法和数据结
构的区别
数据结构和算法数据结构和算法Python版版
算法的提出算法的提出
我们最终写好运行的程序比作战场，我们是将军，Python是士兵和兵器，数据结构和算法则是兵法。
引入
:
第一次尝试
如果 a+b+c = 1000 且a的平方+b的平方等于c的平方(abc都是自然数)，如何求出a、b、c可能的组合?
# 枚举法
# a
# b
# c
import time
a1 = time.time()
for a in range(0,1001): # 进行嵌套
for b in range(0,1001):
for c in range(0,1001):
if a+b+c == 1000 and a**2 + b**2 == c**2: # 同时符合
print('a,b,c:%d,%d,%d'%(a,b,c))
a2 = time.time()
print('经过了',a2 - a1,'时间')
print('完成')
输出结果:
a,b,c:0,500,500
a,b,c:200,375,425
a,b,c:375,200,425
a,b,c:500,0,500
经过了 104.03584575653076 时间
完成
算法的提出算法的提出:
算法的概念: 算法是处计算机的本质，因为计算机程序本质上是一个算法来告诉计算机确切的步骤来执行一个指定的任务。一
般的，当算法在处理信息时，会从输入设备或者数据的存储地址读取数据，把结果写入输出设备或者某个储存地址供以后使
用。
算法是独立存在的一种解决问题的方法和思想。算法是独立存在的一种解决问题的方法和思想。
对于算法而言，实现的语言并不重要，重要的是思想。
算法五大特性算法五大特性:
输入: 算法具有0个或者多个输入。
输出: 算法至少有一个或者多个输出
有穷性:算法在有限的步骤后会自动结束而不会无限循环，并且每一个步骤可以在可接受的时间内完后完成
确定性:算法的每一步都是有确定的含义，不会出现二义性
可行性:算法的每一步都是可行的，也就是说每一步都是能够执行有限的次数完成
第二次尝试尝试:
# 枚举法
# a
# b
# c
import time
a1 = time.time()
# for a in range(0,1001): # 进行嵌套
# for b in range(0,1001):
# for c in range(0,1001):
# if a+b+c == 1000 and a**2 + b**2 == c**2: # 同时符合
# print('a,b,c:%d,%d,%d'%(a,b,c))
# T(复杂度) = 1000(外层循环的循环体) * 1000(中层循环的循环体) * 1000(最内层循环体的内容) * 2(if内的)
# 如果 a+b+c == 2000 可以把1000换成2000即可 所以:
# T = N * N * N * 2
# 时间复杂度:T(n) = n^3 * 2
# 假如说有:T(n) = n^3 * 10 是跟上面一个数量级(n^3)的
# 可以总结为:T(n) = N^3 * k
# g(n) = n^3 这里n^3就是它的大O表示法 称之为 T(n) = O(g(n))
# 则称为O(g(n))这个算法的渐进时间复杂度，简称为时间复杂度。即为T(n)
# 改进后:
资源评论
