我要评论算法分析
若n1+n2+n3=1000,且n1平方+n2平方=n3平方(n1,n2,n3为自然数),求出所有n1、n2、n3可能的组合?
思路1:
n1 = 0
n2 = 0
n3 = 0
判断n1+n2+n3是否等于1000,之后变n3=1,n3=2,n3=3,… 然后再变n2
那如果变为 n1+n2+n3=2000 了呢？
# 思路1代码实现
import time
start_time = time.time()
for n1 in range(0,1001):
for n2 in range(0,1001):
for n3 in range(0,1001):
if n1 + n2 + n3 == 1000 and n1**2 + n2**2 == n3**2:
print('[%d,%d,%d]' % (n1,n2,n3))
end_time = time.time()
print('执行时间:%.2f' % (end_time-start_time))
# 思路2代码实现
for n1 in range(0,1001):
for n2 in range(0,1001):
n3 = 1000 - n1 - n2
if n1**2 + n2**2 == n3**2:
print('[%d,%d,%d]'%(n1,n2,n3))
算法概念是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策
略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出
算法五大特性：
- 输入 – 具有0个或多个输入
- 输出 – 至少由1个或者多个输出
- 有穷性 – 算法执行的步骤是有限的
- 确定性 – 每个计算步骤无二义性
- 可行性 – 每个计算步骤能够在有限的时间内完成
计算时间复杂度 - 执行计算步骤的次数
思路一：
T = 1000 * 1000 * 1000 * 2
T = n * n * n * 2
T(n) = n ** 3 * 2 --> 则时间复杂度为T(n) 及 n**3 * 2
渐近函数 - 数学概念
- 函数1: T(n) = k* g(n) + c —> k为系数,c为常数
-
函数2: g(n) = n ** 3
特点: 在趋向无穷的极限意义下，函数T(n)的增长速度收到函数g(n)的约束，也为函数T(n)与函数g(n)的特征相似，则称 g(n) 是 T(n) 的渐近函数，大O表示法则使用渐近函数来表示，即: O(g(n))即: O(n^3)。
思路二：
T(n) = n * n * (1+max(1,0))
T(n) = n2 * 2
T(n) = n2
T(n) = O(n**2)
用大O表示法表示为 O(n^2)
时间复杂度分类
1.分类
1）最优时间复杂度 - 最少需要多少个步骤
2）最坏时间复杂度 - 最多需要多少个步骤
3）平均时间复杂度 - 平均需要多少个步骤
我们平时所说的时间复杂度,指的是最坏时间复杂度
2.示例 - 列表元素排序
[3,1,4,1,5,9,2,6] --> 时间复杂度:O(n^2)
[1,2,3,4,5,6,7,8] --> 时间复杂度:O(n)
for i in L:
先扫描一遍,若有序直接退出
时间复杂度变为 n
计算算法的时间复杂度
题目1：
for i in range(n): # 循环次数为 n
print("Hello, World!") # 循环体时间复杂度为 O(1) 此时时间复杂度为 O(n × 1)，即 O(n)。
题目2：
for i in range(n): # 循环次数为 n
for j in range(n): # 循环次数为 n
print("Hello, World!") # 循环体时间复杂度为 O(1) 此时时间复杂度为 O(n × n × 1)，即 O(n^2)。
对于顺序执行的语句或者算法，总的时间复杂度等于其中最大的时间复杂度，对于条件判断语句，总的时间复杂度等于其中 时间复杂度最大的路径 的时间复杂度。
题目3：
for i in range(2, n):
i *= 2
print("%d" % i)
假设循环次数为 t，则循环条件满足 2^t < n。
可以得出，执行次数t = log(2)(n)，即 T(n) = log(2)(n)，可见时间复杂度为 O(log(2)(n))，即 O(log n)。
题目4：
def f(n):
if n == 1:
return 1
elif n == 2:
return 2
else:
return f(n - 1) + f(n - 2) T(n) = T(n - 1) + T(n - 2) 是一个斐波那契数列，该方法的时间复杂度可以表示为 O(2^n)。
本文地址：https://blog.csdn.net/qq_27481087/article/details/107071333
您可能感兴趣的文章:
如您对本文有疑问或者有任何想说的，请点击进行留言回复，万千网友为您解惑！
网友评论