java - 使用迭代器的向量的 BigO

Question

我做了一些研究，但我没有找到一篇好的文章。
我将多个添加Vectors到一个Vector，然后打印它：

Iterator it =vector.iterator();
    while(it.hasNext()){
        System.out.println(it.next());
    }

如何确定此函数的 Big-O 表示法？
例如，如果输出是：

[某事，某事，某事，某事]
[某事，某事，某事，某事，某事]
[某事，某事，某事，某事，某事，某事] [某事，某事，某事，某事，某事，某事，某事] [
某事，某事，某事，某事，某事]
，某事，某事，某事，某事，某事，某事，某事]

我不明白每一行都是一个向量，对于主向量我们需要一个循环，但是对于其中的向量我们不需要一个循环，为什么？

score 2 · Accepted Answer

当你调用toString一个集合（比如 a Vector）时，你会得到一个逗号分隔的列表，用方括号括起来，包含toString该集合中每个元素的。

因此，您的代码正在做的是调用main 中的 each，而main又调用了toString每个元素。所以效率是 O(n)，其中 n是被调用的对象的总数。VectorVectortoStringtoString

score 1 · Accepted Answer

假设你总是遵循这个“阶梯模式”：

如果第一个向量的大小为1，最后一个向量的大小为K，使用求和公式，复杂度为：

K*(K+1)/2

现在，如果第一个向量的大小是 k < K，我们有：

K(K+1)/2 - (k-1)(k)/2

最后，如果我们没有“梯形图”但有 N 个大小 < K 的向量，则复杂度为：

K*N

希望能帮助到你。

2 回答 2