アルゴリズムの複雑さ：より大きい配列のサブ配列の開始インデックスを見つける

Question

questionを参照して、インデックスを取得するためにJava Collections APIを使用した回答が見つかりました。私の質問は、最適な解決策になる、与えられた問題を解決する他の多くの方法があるということですか？

1. 利用二つのループがO(n^2)時間がかかります
2. 使用コレクションAPI

Answer 1

1. 使用をハッシュ
2. 使用をソートとマージ
3. 使用をソートし、バイナリサーチつのループ
4. 使用
5. の使用は、ソート、バイナリ検索がO(nlog n)時間
6. 使用がかかりますO(nlog n)時間をソートおよびマージ
7. 使用ハッシュは、他のいくつかのオーバーヘッドと追加のスペースでO(k * n)時間がかかります。
8. 使用コレクションAPIはnとmであるリニアO(n + m)時間複雑にKnuth–Morris–Pratt algorithmを使用することによってあなたは、上記の方法と一緒に最適な方法でそれを行うことができます

フードの下にその使用ネイティブアルゴリズムとしてO(n^2)時間がかかります2つの配列の長さ

KMPアルゴリズムは基本的に、文字列に作用するパターンマッチングアルゴリズム（ヘイスタックの針の開始位置を見つける）です。しかし、整数配列に簡単に使用できます。

これらの実装すべてについてベンチマークテストを行い、要件に合うように効率的なものを選択できます。