C中函数的复杂性

Question

int f1(int N) {
    int Sum, i, j, k;
    Sum = 0;
    for (i = 0; i < N; i++)
        for (j = 0; j < i * i; j++)
            for (k = 0; k < j; k++)    
                Sum++;
    return Sum;
}

int f2(int N) {
    int Sum, i, j;
    Sum = 0;
    for (i = 0; i < 10; i++)
        for (j = 0; j < i; j++)
            Sum += j * N;
    return Sum;
}

什么是f1和f2？的复杂性？

我不知道复杂性,f1我认为复杂性f2应该是O(1),因为迭代次数是不变的.它是正确的？

Answer 1

你的第一个函数的复杂度为O(N ^(1 + 2 + 2))= O(N ^ 5).

在第一个循环中,i从0开始在N上,第二个j循环超过依赖于N ^ 2的限制,并且在第3个循环中,循环的大小取决于N ^ 2.

函数F2是常数时间,因此O(1)因为循环没有任何自由度.

在"复杂性"主题的算法课程中研究了这种东西.

基于omega符号,还有另一种算法复杂度的测量.