分析算法的时间复杂度 [英] analysing an algorithm for time complexity

问题描述

我写一个函数，将两个链接列表。 （注意：该功能是基于pre-给出的情况下，你想知道为什么我调用一个函数节点（i）code ）。

I have written a function that merges two linked list. (Note that the function is based on pre-given code in case you wonder why i'm calling a function 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）

first part O(n) second part O(n)

整体复杂度为O（n）

或者是为O（n ^ 2），因为我遍历列表两次？

or is it O(n^2) because i traverse the list twice?

推荐答案

由于你走过的列表两次，这是O（2N）..这是O（n）。它是线性增长。

Because you traversed the list twice, it's O(2n).. which is O(n). It is linear growth.

此外，在大多数编程语言，一个集合的长度已经被跟踪，所以你可以只拉两次迭代的那个属性。

Also, in most programming languages, the length of a collection is already tracked, so you can just pull that property instead of iterating twice.

这篇关于分析算法的时间复杂度的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！