algorithm - 分析算法的时间复杂度

Question

我写了一个合并两个链表的函数。 (请注意，该函数基于预先给定的代码，以防您想知道我为什么要调用函数 node(i))。

public SLL mergeUnsorted(SLL otherList)
{
    // find length of this list
    int length = 0 ;
    Iterator itr = this.iterator() ;
    while (itr.hasNext())
    {
        Object elem  = itr.next() ;
        length++ ;
    }

    // get each node from this list and
    // add it to front of otherList list
    int i = length -1 ;
    while (i >= 0)
    {
        // returns node from this list
        SLLNode ins = node(i) ;

        ins.succ = otherList.first ;
        otherList.first = ins ;
        i-- ;
    }
    return this ;
}

第一部分 O(n) 第二部分 O(n)

整体复杂度O(n)

还是 O(n^2) 因为我遍历列表两次？

Answer 1

遍历两次只是一个常量乘数。只要乘数不依赖于 n，它仍然是 O(n)。编辑:但是，请确保插入另一个列表是恒定时间的。如果执行此操作的时间与其他列表的大小成正比，那么，我想您可以看到会发生什么。