java - 複雑度クラス

Question

この問題のビッグオー表記は何ですか? なんで？ここには 1 つのループがあるため、O(N) だと思いますが、よくわかりません。

public static void mystery(List<String> list){

    for(int i = 0; i< list.size()-1; i+=2){

        String first = list.remove(i);

        list.add(i + 1, first);

    }

}

Answer 1

時間計算量は O(n^2) です。

ループは floor(n/2) 回実行されます。List.add(int i) と list.remove(int i) はどちらも平均して O(n) です (以下の理由に関する注を参照してください)。これは、O(n^2) である O(n*n/2) になります。

組み込みの List 実装に関する注意事項

ArrayList で List.add(int i, element) または List.remove(int i) を呼び出す場合、要素を挿入または削除するには、リスト内の要素をシフトする必要があります (リストの最後にない場合)。必要なシフト数は n です。したがって、追加操作と削除操作はどちらも O(n) です。

List.add(int i, element) と List.remove(int i) は、LinkedList で呼び出された場合も O(n) です。これは、要素を削除/追加するために、指定されたインデックスにトラバースする必要があるためです。

特定のリストへの追加/削除がシーケンシャルになることがわかっている場合は、より適切に行うことができます。LinkedList を使用する ListIterator を使用すると、時間の複雑さを O(n) に減らすことができます。add メソッドと remove メソッドは、LinkedLists ListIterator で呼び出されると O(1) になります。これは、指定されたインデックスに移動する必要がないためです。

ListIterator を使用した askers メソッドの実装例

public static void mystery(List<String> list){
    ListIterator<String> iterator = list.listIterator();
    int i = 0;
    while (i < list.size()-1) {
        String first = iterator.next();
        // Remove first
        iterator.remove();
        // Skip an element
        iterator.next();
        // insert at i+1
        iterator.add(first);
        i+=2;
    }
}

Answer 2

O(n^2)のようです。リストを反復処理し、反復ごとにlist.remove()、O(n) でも実行される呼び出しを呼び出します。したがって、この関数の時間計算量は O(n^2) である必要があります。

Answer 3

このメソッドを実行すると、次のように実行されます。

remove 0
append 1
remove 1
append 2
...

リストが配列リストであると仮定します。

すべての要素が常に最後に削除されると仮定する So: n/2 * (2*n + n) = 3 * n^2 /2 => O(n^2)

すべての要素が常に一番上にあると仮定します。したがって: n/2 * (n + n) => O(n^2)

そう。最悪のケースと最良のケースは常に O(n^2) であるため、Big-O だけでなく、複雑さも o(n^2) になります。