参考数学分析里的$O$记号
by Macrohard @ 2019-05-19 12:19:10
**注意常把$\theta$写成$O$**
没有循环的就是$\theta(1)$如`int c = a + b;`
有一层循环的，$\theta(n)$如`for(int i=1;i<=n;i++) a[i]=i;`
嵌套循环，假设有$x$层，那就是$\theta(n^x)$
如
```cpp
for (int i = 1; i <= n; i++)
{
for (int j = 1; j <= n; j++)
{
for (int k = 1; k <= n; k++)
{
for (int l = 1; l <= n; l++)
{
dp[i][j][k][l] = max4(dp[i - 1][j][k - 1][l],
dp[i - 1][j][k][l - 1],
dp[i][j - 1][k - 1][l],
dp[i][j - 1][k][l - 1]) +
mp[i][j] + mp[k][l];
if (i == k && j == l)
dp[i][j][k][l] -= mp[i][j];
}
}
}
}
```
这是$\theta(n^4)$
(P1004 方格取数)
递归的话，看递归式，有几个递归自己的（假设有$s$个）就是$\theta(s^n)$
如
```cpp
int f(int n){
if(n==1||n==2) return 1;
return f(n-1)+f(n-2);
}
```
这是$\theta(2^n)$
~~像我这样认真写Markdown的人已经不多了~~
by Dynamic_Cast @ 2019-05-19 12:29:41
@[LTL_td](/space/show?uid=39824)
~~我@下，怕你看不到~~
by Dynamic_Cast @ 2019-05-19 12:30:47
@[Dynamic_Cast](/space/show?uid=119181) 不是$\Theta$吗？
by t162 @ 2019-05-19 12:39:22
你真是误导别人，那的确是$O(2^n)$，但不是Θ
by cosmicAC @ 2019-05-19 12:58:04
@[Dynamic_Cast](/space/show?uid=119181)
by cosmicAC @ 2019-05-19 12:58:30
@[SarvaTathagata](/space/show?uid=30093) 抱歉
by Dynamic_Cast @ 2019-05-19 13:20:42
我问的是P4570这道题。。。。。
by LTL_td @ 2019-05-19 14:02:19
@SarvaTathagata
by xhQYm @ 2019-11-25 16:13:41
@https://www.luogu.com.cn/user/30093
by xhQYm @ 2019-11-25 16:14:17