算法分析day01

若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)。