java - 使用多个相同的方法和时间复杂度

Question

对于下面的代码块，我想知道它的总时间复杂度是否为 O(n^2) 或更大。我知道链表的 get() 方法运行 O(n) 时间，但是我多次使用它有关系吗？因为我已经使用了 3 次，所以 get() 会是 O(n^3) 还是保持在 O(n)？

public static LinkedList<Integer> merge(LinkedList<Integer> a, LinkedList<Integer> b){
        LinkedList<Integer> c = new LinkedList<>();
        for (int i = 0; i < b.size(); i++) {
            if (i >= a.size()) { // 4
                c.add(b.get(i)); // 4
            }
            else {
                b.add(i, a.get(i));
                c.add(b.get(i));
            }
        }
        return c;
    }

Answer 1

链表实现中的访问是 O(n)。要从列表中添加元素，需要有一个循环遵循从一个元素到下一个元素的链接。在最坏的情况下，在 n 个元素的列表中，将执行循环的 n 次迭代。