46

splice() を使用して配列から 1 つの要素を削除すると、次のようになります。

arr.splice(i, 1);

i の後にすべての要素をシフトするため、これO(n)は最悪のケースになりますか? それとも、下にいくつかのリンクされたリストの魔法がある一定の時間ですか?

4

3 に答える 3

30

最悪の場合は(すべての要素を新しい配列にO(n)コピーする) 必要があります。n-1

リンクされたリストはO(1)、単一の削除用です。

興味のある方のために、この怠惰に作成されたベンチマークを作成しました。( Windows XP/Vista では実行しないでください)。ただし、これからわか​​るように、かなり一定 (つまり ) に見えるO(1)ため、これを非常に高速にするために舞台裏で何をしているのか誰にもわかりません。それにもかかわらず、実際spliceは非常に高速であることに注意してください。

推奨するV8 シェルで拡張ベンチマークO(n)を直接再実行します。ただし、コードに影響を与える可能性があるランタイムを取得するには、巨大な配列サイズが必要であることに注意してください。memmoveこれは、新しい配列を作成するために使用する V8 コードを見ると予想されるはずです。

于 2011-03-03T02:22:22.953 に答える
4

やあ！

私は自分で実験を行ったので、その結果を共有したいと思います。実験は非常に単純で、サイズ n の配列で 100 回のスプライス操作を実行し、各スプライス関数にかかった平均時間を計算しました。次に、n のサイズを変化させて、その動作を確認しました。

このグラフは、大きな数に対する調査結果をまとめたものです。

大きな数の場合、線形に動作するようです。

また、「小さい」数値でチェックしました (それらはまだかなり大きいですが、それほど大きくはありません)。

この場合、それは一定のようです。

1 つのオプションを決定する必要がある場合、それは O(n) であると言えます。ただし、線形の動作は非常に大きな数の場合にのみ表示されることに注意してください。

ただし、javascript での配列の実装は、配列の宣言方法と操作方法に大きく依存するため、決定的な答えを求めるのは困難です。

配列がどのように機能するかを理解するには、このスタックオーバーフローディスカッションとこのクォーラ ディスカッションをお勧めします。

ノード v10.15.3 で実行します。使用されるコードは次のとおりです。

const f = async () => {
  const n = 80000000;
  const tries = 100;
  const array = [];
  for (let i = 0; i < n; i++) { // build initial array
    array.push(i);
  }
  
  let sum = 0;
  for (let i = 0; i < tries; i++) {
    const index = Math.floor(Math.random() * (n));
    const start = new Date();
    array.splice(index, 1); // UNCOMMENT FOR OPTION A
    // array.splice(index, 0, -1); // UNCOMMENT FOR OPTION B
    const time = new Date().getTime() - start.getTime();
    sum += time;
    array.push(-2); // UNCOMMENT FOR OPTION A, to keep it of size n
    // array.pop(); // UNCOMMENT FOR OPTION B, to keep it of size n

  }
  console.log('for an array of size', n, 'the average time of', tries, 'splices was:', sum / tries);
 };
f();

コードにはオプション B があることに注意してください。要素を挿入するために、3 つの引数 splice 関数に対して同じ実験を行いました。同様に機能しました。

于 2021-05-18T14:45:59.307 に答える