Python版数据结构算法教程（一）：算法概述是怎样的？

本文共计498个文字，预计阅读时间需要2分钟。

1. 时间复杂度：时间复杂度：O(1)、O(logn)、O(n)、O(nlogn)、O(n+2)、O(n+2logn)、O(n+3)、2

2. 判断时间复杂度方法：确定问题规模：n分析算法执行步骤：- 线性结构：O(n)- 二分查找：O(logn)- 循环递减：logn- 递归调用：O(nlogn)- 空间复杂度：O(1)到O(n)

1、时间复杂度

• 时间复杂度：用来评估算法运行效率的一个式子
• 常见的时间复杂度排序
  O(1)<O(logn)<O(n)<O(nlogn)<O(n²) <O(n²logn)<O(n³)

2、判断时间复杂度方法

• 确定问题规模：n
• 循环减半：logn
• k层关于n的循环：n^k
• 复杂情况：根据算法执行过程判断

3、时间复杂度举例

• 如下代码,时间复杂度为O（1）

print("hello world")

• 如下代码，时间复杂度为O（n）

for i in range(n):
print("hello world")

• 如下代码，时间复杂度为O（n²）

for i in range(n)
for j in range(n):
print("Hello world")

• 如下代码，每次循环减半的时候，时间复杂度为O（logn）

while n>1:
print(n)
n//=2

4、空间复杂度

• 空间复杂度：用来评估算法内存占用大小的式子
• 空间复杂度的表示方式与时间复杂度完全一样

• 算法使用了几个变量：O（1）
• 算法使用了长度为n的一组列表：O（n）
• 算法使用了m行n列的二维列表：O（mn）

• 通常情况下经常会以空间换时间