0

私のアルゴリズムのクラスでは、整数のリストの重複を削除するアルゴリズムを導入し、可能な限り複雑さを軽減する必要があります。私のアルゴリズムでは、重複する整数が表示されると、for ループを使用して重複した要素を削除するために、その整数の後のすべての要素を 1 インデックス下にシフトします。そのようです：

for(int i=dup_index; i<arr_size-1; i++)
{
  arr[i] = arr[i+1];
}

アルゴリズムが memmove を使用する方が効率的でしょうか? さらに、アルゴリズムを設計することが私の仕事であり、memmove がアルゴリズムの複雑さを軽減すると仮定すると、memmove の使用は「不正行為」と見なされる可能性がありますか?

4

5 に答える 5

0

機能的には、 memmove はループが行うこととまったく同じことを行います。ただし、コンパイラや C ランタイムは、より効率的なマシン コードを使用して memmove を実装する場合があります。一部のアーキテクチャには、このような操作を 1 つの命令で完全に実行する特殊な命令があります。コンパイラによってインライン化される場合もあります。

アルゴリズムの複雑さは変わらず、処理が速くなるだけです。

それがあなたの宿題でカンニングとみなされるかどうかについては、それはあなたの教授への質問ですよね? ここでは誰もあなたにそれを言うことはできません.

于 2014-02-08T03:02:02.730 に答える
0

ライブラリ関数 ( などmemmove(3)) は慎重に最適化されています。お気に入りのコンパイラがさまざまな長さ (定数として与えられたもの) でそれをアセンブリ言語に書き出す方法を見ると、おそらく大きな驚きを覚えるでしょう。

とはいえ、ある場所から別の場所に $n$ バイトをコピーするには、$\Theta(n)$ という時間がかかります。ただし、データをシャッフルする一部を回避するのに役立つ何かを知っている場合を除きます。 .

于 2014-02-08T16:54:45.820 に答える