分析时间复杂度的算法

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).编辑:但是,请确保插入其他列表是恒定时间.如果这样做的时间与另一个列表的大小成正比,那么我认为你可以看到当时会发生什么.