5

I've a uni practical to determine the complexity of a small section of code using the O() notation.

The code is:

for (int i = 0; i < list.size(); i++)
    System.out.println(list.get(i));

The list in question is a linked list. For our practical, we were given a ready made LinkedList class, although we had to write our own size() and get() methods.

What is confusing me about this question is what to count in the final calculation. The question asks:

How many lookups would it make if there 100 elements in the list? Based on this, calculate the complexity of the program using O() notation.

If I am just counting the get() method, it will make an average of n/2 lookups, resulting in a big O notation of O(n). However, each iteration of the for loop requires recalculating the size(), which involves a lookup (to determine how many nodes are in the linked list).

When calculating the complexity of this code, should this be taken into consideration? Or does calculating the size not count as a lookup?

4

4 に答える 4

8

答えるのが少し遅れるかもしれませんが、この for ループは実際には次のようになると思いますO(n^2)

説明

リストの i 番目のインデックスにアクセスする各ループ反復。したがって、呼び出しシーケンスは次のようになります。

順序

これは、各反復iがインクリメントされ、n回ループしているためです。

したがって、メソッド呼び出しの総数は、次の合計を使用して評価できます。

ここに画像の説明を入力

于 2016-12-10T00:10:31.353 に答える
4

Java LinkedList では、get(int) 操作は O(N)、size() 操作は O(1) の複雑さです。

于 2015-12-20T00:21:16.653 に答える
2

これはリンクされたリストであるため、リスト全体をトラバースする必要があるため、サイズを決定するには O(N) 操作になります。

また、.get() の時間計算量を誤って計算しました。big-O の場合、重要なのは最悪の場合の計算です。リンクされたリストの場合、取得の最悪のケースは、要素がリストの最後にあるため、これも O(N) です。

全体として、アルゴリズムは反復ごとに O(2N) = O(N) 時間かかります。そこから、ループ全体の時間の複雑さがどのくらいになるかを理解していただければ幸いです。

ところで、現実の世界では、ループの前にサイズを 1 回だけ計算する必要があります。これは、まさにこのように非効率的である可能性があるためです。明らかに、リストのサイズがループ中に変更される可能性がある場合、それはオプションではありませんが、この非変更アルゴリズムの場合はそうではないようです。

于 2013-03-04T00:15:52.780 に答える