O(n³)

一句话理解

O(n³) 三层循环，n=200 左右才比较安心。

为什么要学

Floyd、简单区间 DP、朴素矩阵乘法。

讲解

200³=8e6，400³=6.4e7，500³=1.25e8。卡常的时候 400 都可能慢。

看到 n≤400 要想是不是 n³。

例子

Floyd 三重循环枚举 k,i,j，就是 O(n³)。

常见错误

• n=1000 写 Floyd。
• n=300 再乘一个大常数。