なぜこのO（n^2）ソリューションはO（n）ソリューションより速く動作するのですか？

Question

編集：申し訳ありません私は不注意で同じコードをコピー＆ペーストしたようです。

---

質問：

0からN-1までの数値のリストを考えると、あなたの仕事が見つからない 番号を見つけることです。あなたのプログラムは整数のリストを取り、 の単一の整数（欠けている数）を返します。

つまり、[0, 1, 3, 4, 5]の入力は2を返す必要があります。

O（n）で1つ、（On^2）で1つの解決策が見つかりました。

O（N）溶液

def alt_find_missing(input_list): 
    input_sum = sum(input_list) 
    range_sum = sum([i for i in range(min(input_list), max(input_list)+1)]) 
    return range_sum - input_sum 

はO（n^2）溶液

def find_missing(input_list): 
    input_set = set(input_list) 
    for i in range(min(input_list), max(input_list)+1): 
     if i not in input_set: 
      return i 

しかしながら、O（N^2）の溶液を（高速Oより実行n）複数の試験でtimeit試験：

List with 4 elements, using for ... in set (x 1 000 000) 
1.1550223514080038 
List with 4 elements, using difference of sums (x 1 000 000) 
1.391524411772641 
List with 100 elements, using for ... in set (x 1 000 000) 
8.43574248785071 
List with 100 elements, using difference of sums (x 1 000 000) 
8.94695660741872 
List with 1000 elements, using for ... in set (x 100 000) 
8.1138781071155 
List with 1000 elements, using difference of sums (x 100 000) 
8.383110816298519 

これはなぜですか？

Answer 1

第2のアルゴリズムはO（n^2）ではありません。セットルックアップはO（1）であり、セットに対する反復はO（n）である。したがって、2つのアルゴリズムの違いは、さまざまな定数要因によるものです。ここで

は結果が私にはかなり直線的に:)に見える確かにいくつかの問題の大きさで起こって奇妙な何かがありませんが、かなり出て結果を投げるためには何も

import timeit 
from functools import partial 
from matplotlib import pyplot as plt 

def alt_find_missing(input_list): 
    input_sum = sum(input_list) 
    range_sum = sum([i for i in range(min(input_list), max(input_list)+1)]) 
    return range_sum - input_sum 


def find_missing(input_list): 
    input_set = set(input_list) 
    for i in range(min(input_list), max(input_list)+1): 
     if i not in input_set: 
      return i 


t1=[] 
t2=[] 

rng=range(10000,1000000,10000) 

for n in rng: 
    func1=partial(find_missing,range(n)) 
    func2=partial(alt_find_missing,range(n)) 
    t1.append(timeit.timeit(func1,number=5)) 
    t2.append(timeit.timeit(func2,number=5)) 

plt.plot(rng,t1, label='Find missing') 
plt.plot(rng,t2, label='Alt find missing') 
plt.ylabel('Execution time') 
plt.xlabel('Problem size') 
plt.legend() 
plt.show() 

両方の機能の線形挙動を示した短いスクリプトですリニアリティゾーンの

よろしくお願いいたします。