算法複雜性：查找較大陣列中子陣列的起始索引

Question

參考question，我發現接受的答案使用Java Collections API來獲取索引。我的問題是有很多其他方法來解決給定的問題，這將是最佳的解決方案？

1. 使用兩個循環
2. 使用排序和二進制搜索
3. 使用排序和合並
4. 使用散列
5. 使用集合API

Answer 1

1. 使用兩個環路將採取O(n^2)時間
2. 使用排序和二進制搜索將耗費O(nlog n)時間
3. 使用排序和合並O(nlog n)時間
4. 使用散列將O(k * n)時間與其他一些開銷和額外的空間。
5. 使用集合API將O(n^2)時間作爲其使用原生算法引擎蓋下

你可以做到這一點的最佳方式與上述方式沿着線性O(n + m)時間複雜度，其中n和m使用Knuth–Morris–Pratt algorithm兩個陣列的長度。

KMP算法基本上是一種對字符串起作用的模式匹配算法（查找haystack中針的起始位置）。但是你可以很容易地將它用於整數數組。

您可以對所有這些實現進行一些基準測試，並選擇哪一個足夠高效以滿足您的要求。