python算法与数据结构（算法的时间复杂度）

算法分析

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

算法概念是指解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表着用系统的方法描述解决问题的策
略机制。也就是说，能够对一定规范的输入，在有限时间内获得所要求的输出

算法五大特性：

1. 输入 – 具有0个或多个输入
2. 输出 – 至少由1个或者多个输出
3. 有穷性 – 算法执行的步骤是有限的
4. 确定性 – 每个计算步骤无二义性
5. 可行性 – 每个计算步骤能够在有限的时间内完成

计算时间复杂度 - 执行计算步骤的次数

思路一：
T = 1000 * 1000 * 1000 * 2
T = n * n * n * 2
T(n) = n ** 3 * 2 --> 则时间复杂度为T(n) 及 n**3 * 2

渐近函数 - 数学概念

1. 函数1: T(n) = k* g(n) + c —> k为系数,c为常数
2. 函数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