第2课：时间复杂度初识
进度 0/24
⚡
时间复杂度初识
学会给程序计时，做懂效率的高手！
📖知识引入
⏱️为什么要计时
数据量一大，快算法与慢算法差距是几百上千倍
📈大O记号
用O(…)描述运算次数随数据量增长的趋势，是大致的量级
🚀常见量级
O(1)常数最快，O(n)线性，O(n²)平方，n越大差距越夸张
🔍数循环层数
初学技巧：单层循环常是O(n)，嵌套两层常是O(n²)
💡
信奥题面常给n的范围：n≤1000时O(n²)能过，n≤10⁵就要想O(n log n)的办法
🔍O(n) 与 O(n²) 的对决
// O(n)：循环一遍求和，100个数只需100步
long long sum = 0;
for (int i = 1; i <= n; i++) sum += i;
// O(n²)：两重循环数对数，100个数要10000步
int cnt = 0;
for (int i = 1; i <= n; i++)
for (int j = i + 1; j <= n; j++)
cnt++; // 数出所有数对n=100时一个是100步、一个是一万步，n=10⁵时O(n²)直接超时
🎯小测验
第1题：O(1)表示算法耗时有什么特点？
第2题：两重嵌套循环每层都执行n次，复杂度通常是？
第3题：下列哪个复杂度量级最慢？
📝本课知识点
- ✓大O记号描述增长趋势
- ✓O(1)最快，O(n²)易超时
- ✓先数循环层数，粗估复杂度
第2课完成！继续探索下一课吧 🚀