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

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个循环的迭代。