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

我有下面的方法，我想知道大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;
        }

我知道循环的第一个是复杂的O(n)，而第二个while循环具有复杂的O(n^2)。在这种情况下，我们是否放弃了第一个O(n)并保持第二个O(n^2)，并说这种方法具有复杂的O(n^2)？还是我们保留它并说它有复杂的O(n + n^2)？

最佳答案

你保持了增长率最大的部分，所以O（n^2）。