0

単一リンクリストの疑似コードをいくつか書きました。この関数は、キー (k) の出現ごとに、前の要素のキーの値を増やす必要があります。唯一の例外は、最初の要素 (変更されていない) です。

List-Increase-Key(L,k)
    x = L.head
    k = L.head
    while (x.key != k and x != NIL)
        prex = x.key
        x = x.next
        if x.key == k
            x.key = x.key + prex

リスト全体を1回トラバースするため、実行時間はO(n)だと思います。私の時間の複雑さの見積もりが正確かどうか、またはこれがそれよりも効率的かどうか疑問に思っています。または、私のアイデアががらくたで、クラッシュして恐ろしく燃えると思うなら。お立ち寄りいただきありがとうございます。

4

1 に答える 1

0

単一のトラバーサルが行われるため、実行時間は明らかに O(n) です。

しかし、私はあなたのコードにいくつかの格差を見つけました。

while (x.key != k and x != NIL)

上記のステートメントでは、NIL チェックは条件"x.key!=k"に先行する必要があります。

于 2013-06-07T05:07:16.420 に答える