以下方法的 Big-O 复杂度是多少？

Question

下面有一个方法，想知道大O的复杂度。

public FinalPrepDeque<E> listUnion(FinalPrepDeque<E> lst2) {

          FinalPrepDeque<E> lst3 = new FinalPrepDeque<E>();

          Iterator<E> it1 = this.iterator();

          while (it1.hasNext()) { // O(n)
              E val = it1.next();
              if (val != null)
                  lst3.addLast(val);
          }

          Iterator<E> it2 = lst2.iterator();

          boolean found;
          while (it2.hasNext()) { // O(n)
            E val2 = it2.next();
            if (val2 != null) {

            found = false;
            it1 = this.iterator();

            while (it1.hasNext()) { // O(n)
              E val1 = it1.next();
              if (val1 != null) {
              if (val1.equals(val2)) {

                found = true;
                break;
              }
             }
            }
            if (!found)
              lst3.addLast(val2);

          }
          } // end outer-while

          return lst3;
        }

我知道第一个 while 循环的复杂度为 O(n)，第二个 while 循环的复杂度为 O(n^2)。在这种情况下，我们是否删除第一个 O(n) 并保留第二个 O(n^2) 并说此方法的复杂度为 O(n^2)？或者我们保留它并说它的复杂度为 O(n + n^2)?

Answer 1

你保留了增长率最大的部分，所以O(n^2)。

Answer 2

使用大 O 表示法，您有：

n1 + n2 * n3 = n + n^2 = O(n + n^2) = O(n^2)

n1 是第一个 while，n2 是第二个 while，n3 是第三个 while第二.

以下方法的 Big-O 复杂度是多少？

What is the Big-O complexity of the following method?

algorithm

big-o

while-loop