嵌套、依赖 for 循环：求和公式和大 O 符号

Question

在这里工作时间紧迫。努力理解这个问题到底在问什么。任何正确方向的帮助或指示将不胜感激！先谢谢了。原始问题基于此给定信息：

for (int k = 0; k < 2*n; k++) {
    cout << k << endl;  
    for (int i = k+1; i < n; i++) 
        { 
            m[i][j] = a[i][j] + b[i][j];
            cout << m[i][j] << endl; 
        } 
    cout << i * k << endl;
}

对于 T(n) = http://www4c.wolframalpha.com/Calculate/MSP/MSP63941h503ff0a609230100002eieg6bhfe5gi70g?MSPStoreType=image/gif&s=23&w=167.&h=49。

这是我的问题：

修改上面的代码，找出基本操作发生的次数（即它在内部for循环中进行了多少次？）。

包括

使用命名空间标准；

int main()  
{ 
    int count = 0;  
    int n = 10; 
    for (int k = 0; k < 2*n; k++) { 
        cout << "outer: " << k << endl; 
        for (int i = k+1; i < n; i++) { 
            cout << "\tinner: " << i << endl; 
            count++;  
        }  
    }  
    cout << count << endl; 
}

根据第 1 步的输出写一个求和
据此，T(n)等价于O(n)还是O(n^2)

我对第 2 部分的具体要求感到困惑。但是我发现：

http://www4c.wolframalpha.com/Calculate/MSP/MSP4561hgb5f47a07e05g00000112a53ahh0670che?MSPStoreType=image/gif&s=30&w=109.&h=49.

对我来说这看起来像 O(N^2)？

对于格式问题，我深表歉意。我在移动。

Answer 1

让我看看我是否指导： 1.我觉得里面的count应该是这样的：

 int main()   { 
     int count = -1;  
     int n = 10; 
     for (int k = 0; k < 2*n; k++) { 
         count = 0;
         cout << "outer: " << k << endl; 
         for (int i = k+1; i < n; i++) { 
             cout << "\tinner: " << i << endl; 
             count++;  
         }  
         cout << count << endl; //<<<here 
     }  
 }

现在收集输出（@here 标记）并形成求和公式。我认为这是任务#2。
根据您的公式（或求和），您将能够概括它是 o(n) 还是 o(n^2)。

这绝对不是线性的。

嵌套、依赖 for 循环：求和公式和大 O 符号

Nested, dependant for loops: Summation formula and Big-O notation

big-o

包括