计算运算以产生多项式

Question

我正在努力准确计算此方法的运算次数，以生成多项式 f(x):

public static int numOccurrences(int n){   
    int count = 0;  
    for(int i = 0; i < n; i++){   
        for(int j = 0; j < n; j++){    
           if(i == j) {
              continue; 
           }       
           if(strings[i] == strings[j]){
              count++;    
           }   
        } 
     }  
    return count; 
}

到目前为止，这是我的理解：

    int count = 0;  //1 time
    int i = 0;      //1 time
    while(i < n)    //n times
    int j = 0;      //n times
    while(j<n)      //n*n times 
    if(i == j)      //n*n times
    continue;       //n times
    if(strings[i] == strings[j]) //n*n+2 times
    count++;        //n*n times  
    i++             //n*n times
    j++             //n*n times
    return count;   //1 time
   

我们位于带有 if 语句的嵌套循环内，我想知道如果我上面的内容不正确，我如何计算操作？

另外，对于

if(strings[i] == strings[j])

行，我为测试数 1，为抓取

strings[i]

数 1，为

strings[j]

数 1。这是正确的吗？

我的最终答案是：f(x) = 5n^4+10n^3+3n+3

如果这是极其错误的，我真诚地道歉！

Answer 1

我想分享我的答案，以防万一有人偶然发现这篇文章。 我今天从导师那里发现的一种生成多项式的更简单的方法是对每个操作进行计数，但是我们不会写出循环内的所有内容都发生了 n*n 次，而是简单地计算单个步骤并嵌套这些单独的步骤n 内的步骤（如 i++）。 例如：

int count = 0;  //1 
int i = 0;      //+ 1 
while(i < n)    //+ n(
i++;            //+ 1
int j = 0;      //+ 1
while(j < n)    //+ n(
j++             //+ 1
if(i == j)      //+ 1
continue;       //+ 1
if(strings[i] == strings[j]) //+ 3
count++;        //+ 1
return count;   //+ 1

将它们全部相加，得到 = 1+1+n(1+1+n(1+1+1+3+1))+1

化简 = 6n^2+2n+3

Answer 2

如何找到算法的时间复杂度？

所以我学到了：

问题是“这个循环会执行多少个操作？”

for(int i=9 ; i>=1 ; i--)

根据多个用户数量为20个

1.) 将 i 设置为 9 就是 1 检查 i>=1 将执行 10 次 i-- 将被执行 9x

2.) 在本例中 n=10，因为 i>=1， 如果 i>0，n 将为 9

i 将被设置为 0，即循环停止时 9到0是10次检查

3.) i-- 是 9 而不是 10，因为在第 10 次检查时它不会执行。

我猜等式是 (1)+(n)+(n-1)

我假设如果循环体是 {算了

我对此不确定（array[i]==arr[j]） 但“[]”是一个访问运算符，它被计为1，“==”被计为1。 总共：3<<"Amogus";} then it's (n-1)*(1)

我希望这会有所帮助，我正在努力传播这个消息，你可能会在这里绊倒，我猜XD必须获得额外的信誉。

如果你想聊天，我的 Reddit 用户名是 Jirudodian。我只是一名二年级 IT 学生，当课程变成寻宝游戏时，我感到很沮丧。