为什么这个时间复杂度是O(n)？

Question

为什么下面的函数时间复杂度为O(n)？我真的无法理解。

void setUpperTriangular (
    int intMatrix[0,…,n-1][0,…,n-1]) {
        for (int i=1; i<n; i++) {
            for (int j=0; j<i; j++) {
                    intMatrix[i][j] = 0;
            } 
        }
    }
}

我不断地得到O(n^2)的最终时间复杂度，因为：

i: execute n times{//Time complexity=n*(n*1)
    j: execute n times{ //Time complexity=n*1
        intMatrix[i][j] = 0; //Time complexity=1
    }
}

- J. Woodring

---

它是O(n²)，谁告诉你它是O(n)？ - Filipp Voronov

你的教授错了！ - Hong Wei Wang

如果你的教授无法解决这个问题，那我会感到担忧。 - Simeon Visser

@J.Woodring 哇哦 - 按照她的逻辑，我只需要重新定义s = log(n)并创建一个O(log(s))排序算法！[注意：实际答案可能是其他的，这只是一个猜测] - Alnitak

@Alnitak，你缺乏前瞻性，我将设置s=-1并创建第一个算法，在开始之前就完成了。 - devrobf

Answer 1

这段代码在数组中遍历了n^2/2个位置（半个方阵），所以它的时间复杂度为O(n^2)

- Navin

Answer 2

这与插入排序的for循环相同。插入排序的时间复杂度为O(n2)。

- user918603

Answer 3

它最多可以被认为是O(n.m)，最终归结为O(n.n)或O(n^2)。

- Prabh_chandhar

Answer 4

所以，计算机科学系主任用不同的方式解释了它。他说，由于第二个循环没有迭代n次，而是迭代n!次。因此从技术上讲，它是O(n)。

- J. Woodring

---

什么是n!？代表阶乘吗？第二个循环总共迭代n(n-1)/2次，每次第一个循环迭代时都有“i”次迭代。 - Filipp Voronov

是的，这意味着阶乘。 - J. Woodring

它不会迭代“n！”次数！！ - Filipp Voronov

这完全是错误的，根本没有阶乘。而且，n！比n大，所以它会以某种方式变成n乘以n！？ - Simeon Visser

@J.Woodring 请指名道姓（大学的名字，而不是教授的名字） - Alnitak

@Alnitak 西佐治亚大学 - J. Woodring