分析算法的时间复杂度

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

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