我相信下面的代码是n^3的大的theta,这是正确的吗?运行时间复杂度
for (int i = 0; i < n; i ++)
{ // A is an array of integers
if (A[i] == 0) {
for (int j = 0; j <= i; j++) {
if (A[i] == 0) {
for (int k = 0; k <= j; k++) {
A[i] = 1;
}
}
}
}
}
而且,以下是n日志(n)的大THETA
for (int i = 1; i < n; i *= 2)
{
func(i);
}
void func(int x) {
if (x <= 1) return;
func(x-1);
}
因为for循环会跑的log(n)次,FUNC最多n递归调用运行。
感谢您的帮助!