algorithm - 配列比較法の時間計算量

Question

1つの1次元配列を2次元配列のすべての行と比較して、それらが等しいかどうかを確認するメソッドがあります。両方の配列には同じ数の列があります。たとえば、{1,0}と{{1,0}、{1,1}}-{1,0}を{1,0}と比較し、次に{1,1}と比較します。2次元配列にn行、両方の配列にm列がある場合、時間計算量はどのくらいになりますか？O（mn）ですか？

Answer 1

特定のインデックスの要素が異なる場合、2つのベクトルの比較は早期に解決できます。したがって、非常に不均一に分散されたデータがない限り、単一のベクトルの比較はO(1)、ベクトルが異なり、O(m)等しい場合に行う必要があります。したがって、全体的な時間計算量は、一致するものO(n + m)と一致しO(n)ないものがある場合になります。もちろん、これは平均して、最悪の場合はO（mn）になります。