分析算法的时间复杂度

分析算法的时间复杂度

本文介绍了分析算法的时间复杂度的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我写一个函数,将两个链接列表。 (注意:该功能是基于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.

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

08-20 20:27