c-此功能运行多少次

Question

int fun_3(int a[], int n){
int sum = 0;
for (i=0 ; i<n ;i++){
for (j=0 ; j<n ; j++){
for (k=0 ; k<n ; k++){
if (a[i] > 100)
sum += 1;
return sum;
}

我计算了该代码最坏情况下的运算次数，除以加法运算、比较运算和赋值运算(不考虑运算时间(。

分配操作：

int sum=0->1操作

对于(i＝0；；(->1操作

对于(；；i++(->n操作

对于(j＝0；；(->n操作

对于(；；j++(->n^2操作

对于(k=0；；(->n^2操作

对于(；；k++(->n^3操作

sum+＝1->n^3操作

分配中的总操作数=2n^3+2n^2+2n+2

添加操作：

对于(；；i++(->n操作

对于(；；j++(->n^2操作

对于(；；k++(->n^3操作

sum+＝1->n^3操作

加法运算总数=2n^3+n^2+n

比较操作：

对于(；i<n；(->n+1

对于(；j<n；(->n(n+1(->n^2+n

对于(；k<n；(->n^2(n+1(->n^3+n^2

如果(a[i]>100(->n^3

比较中的总操作=2n^3+2n^2+2n+1

此代码的操作总数=6n^3+5n^2+5n+3

但是我的大学同事的成绩和我的成绩是不一样的。我想知道我计算的是对是错。

Answer 1

您应该只假设更大的指数，而不是常数。你应该知道如何在计算机科学中报告代码的时间复杂性。阅读大O符号Here Wiki链接或Here GFGlink
首先，您应该分配i, j, k。

现在你有了类似的东西：

int fun_3(int a[], int n){
int sum = 0;
for (int i=0 ; i<n ;i++) {
for (int j=0 ; j<n ; j++) {
for (int k=0 ; k<n ; k++) {
if (a[i] > 100)
sum += 1;
return sum;
}

在最坏的情况下，该代码操作O(n³(操作。