ディクショナリランタイム（Codility Test）

Question

Pythonで答えるコーディングサンプルの質問を試みました。大規模なデータセットでは時間通りに終了できなかったので、私は100点を得ていません。

Nの整数からなる非空ゼロインデックス配列Aが与えられる。

次の質問です。 配列Aの最初の接頭辞は、0≦P < Nのような最小の整数Pであり、配列A [0]、A [1]、...で配列が発生するすべての値も同様に発生します。 A [P]。例えば

、以下の5素子アレイAの第1の被覆接頭辞：

A[0] = 2 A[1] = 2 A[2] = 1 
A[3] = 0 A[4] = 1 

は3は、[2, 2, 1, 0]に等しいシーケンス[ A[0], A[1], A[2], A[3] ]ので、配列Aに発生するすべての値を含ん

私の答えは次のとおりです。

def ps (A): 
    N = len(A); 
    if N == 0: return -1 
    bit = {} 
    for i in range(N): 
     if not A[i] in bit.keys(): 
      bit[A[i]] = 1 
      P = i 
    return P 

結果：：

それはそれは私のアルゴはO（N ** 3）であると考えるので、私は、この質問の100を与え、テストケースを失敗していませんが、分析

random_n_log_100000 
random test 100 000 elements and n/log_2 n values. 10.025 s. TIMEOUT ERROR 
running time: >10.02 sec., time limit: 9.82 sec. 

random_n_10000 
random test 10 000 elements and values. 1.744 s. TIMEOUT ERROR 
running time: >1.74 sec., time limit: 1.10 sec. 

random_n_100000 
random test 100 000 elements and values. 10.025 s. TIMEOUT ERROR 
running time: >10.02 sec., time limit: 9.94 sec. 

ですまず

1. 私は信じている私のコードは、私は自分のコードの重要な部分を想定して、A [i]がbit.keys（）で、一定の実行時間を持っているO（N）である、すなわちO（1） 。しかし、おそらく大規模なデータセットでは、ハッシュ関数は多くの衝突を与えるので、ランタイムはもはやO（1）ですか？

2. O（N ** 3）はO（N^3）を意味しますか？コーディネリティがN square algoをO（N^2）として報告する他のポストを見ているので、私はこの質問を持っています。だから私は彼らが彼らの報告書で一貫していると思いますか？

3. 本当に私の答えがO（N^3）だと思うのであれば、私のコードは期限を過ぎて1秒未満しか動かないので妥当でしょうか？ここでは、O（N）algoの時間制限は、これが質問で要求されているためだと仮定します。そうだとすれば、O（N^3）の孤独がちょうど> 1秒遅いのはなぜですか？

Answer 1

bit.keys()がリストです。要素がリスト内にあるかどうかのテストはO（n）です。 一方、要素がdictにあるかどうかのテストはO（1）です。 だから、この変更により

if not A[i] in bit: 

へ

if not A[i] in bit.keys(): 

を変更、私はあなたのアルゴリズムはO（n）があると信じています。

（変更がなければ、私はないはO（n^3）、あなたのアルゴリズムはO（N^2）であると考えています。）

Answer 2

Tried C# code. dont know if it will work for higher values 



class Program 
{ 
    static void Main(string[] args) 
    { 
     int[] A = {2,1,1,0,3}; 
     int i ,n=A.Length; 
    for (i= 0; i<n;i++) 
    { 
     if (A.Contains(i)) 
     { 
      // 
     } 
     else 
     { 
      int p = i; 
     } 


    } 
    Console.WriteLine("p not found"); 

    } 
}