时间复杂度

算法教程 · 第 2 章 · 5 次浏览

时间复杂度是算法随输入规模增长所需时间的增长趋势。学会分析它，才能比较不同写法的优劣。

分析规则

只看最高阶项：O(2n+100) = O(n)
忽略常数系数：O(3n²) = O(n²)
循环嵌套相乘：外层 n 次 × 内层 n 次 = O(n²)
循环次数减半：i *= 2 是 O(logn)

常见复杂度

O(1) 哈希查、O(logn) 二分/平衡树、O(n) 单层循环、O(nlogn) 快排/归并、O(n²) 冒泡/双重循环。

代码示例

# 各复杂度示例
def o1(arr):           # O(1)
    return arr[0]

def on(arr):           # O(n)
    total = 0
    for x in arr:
        total += x
    return total

def on2(arr):          # O(n²)
    n = len(arr)
    for i in range(n):
        for j in range(n):
            pass

def ologn(n):          # O(logn)
    count = 0
    while n > 1:
        n //= 2
        count += 1
    return count

# 比较：n=100000 时
# O(n) 十万次 vs O(n²) 百亿次 vs O(logn) 17 次

📚 Python 语法速查

常用条目速查，完整版见对应教程章节。可复制代码到在线运行中测试。

写法 / 语法	作用
`print("hello")`	输出到控制台
`name = "张三"`	变量赋值（无需声明类型）
`if x > 0: ...`	条件判断（注意冒号和缩进）
`for i in range(10): ...`	循环（缩进是语法的一部分）
`while x < 10: ...`	条件循环
`def fn(a, b): return a + b`	定义函数
`class Person: ...`	定义类
`list = [1, 2, 3]`	列表（可改）
`tuple = (1, 2)`	元组（不可改）
`dict = {"key": "value"}`	字典（键值对）
`set = {1, 2, 3}`	集合（去重）
`len(obj)`	取长度
`str(x) / int(x) / float(x)`	类型转换
`s.split(",")`	字符串按分隔符拆分
`" ".join(list)`	列表拼接成字符串
`import os`	导入模块
`from math import sqrt`	从模块导入指定函数
`try: ... except Exception as e: ...`	异常捕获
`with open("a.txt", "r") as f: ...`	文件读取（自动关闭）
`f"你好 {name}"`	f-string 格式化
`lambda x: x * 2`	匿名函数
`list(map(fn, arr))`	函数式处理列表
`range(start, stop, step)`	生成数字序列
`if __name__ == "__main__":`	主入口判断
`pip install 包名`	安装第三方包（命令行）