私が言及しているアプローチは、デュアルポインタ技術です。ここで、最初のポインターは単純なイテレーターであり、2番目のポインターは最初のポインターに関連する以前のすべての値のみを通過します。
そうすれば、ノードごとに他のすべてのノードと比較した場合よりも、実行される作業が少なくなります。これは最終的にO（n ^ 2）になります。
私の質問は、デュアルポインタ方式の速度とその理由です。
1 に答える
4
したがってN、リストに要素がある場合、要素の重複排除を行うには比較iが必要になります（その背後に値があります）。したがって、比較の総数をとして設定できます。この合計は、に評価されます。これは、の場合よりも厳密に小さくなります。iisum[i = 0 to N] iN(N+1)/2N^2N > 1
編集：合計を解決するには、次のようにアプローチできます。
1 + 2 + 3 + 4 + ... + (n-2) + (n-1) + n ここから、反対側の数字を一致させることができます。これはその後になることができます
2 + 3 + ... + (n-1) + (n+1)1開始時と終了時を一致させることによってn。とで同じことを2行い(n-1)ます。
3 + ... + (n-1+2) + (n+1)になります
3 + ... + (n+1) + (n+1)
n/2毎回2つの数字を一致させているので、この回数を繰り返すことができます。これn/2により、用語の出現が残り(n+1)ます。それらを掛けて単純化すると、(n+1)(n/2)またはが得られn(n+1)/2ます。
詳細については、こちらをご覧ください。
また、これは、この合計がまだのビッグシータを持っていることを示唆していn^2ます。
于 2011-07-28T18:51:54.800 に答える