使用多种相同的方法和时间复杂度

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(。要从列表中add元素，有一个循环跟随从一个元素到下一个元素的链接。在最坏的情况下，在n元素列表中，执行循环的n迭代。