java - Java 搜索算法

Question

任何人都可以通过以下实现告诉 java 示例/算法在数组中搜索元素：
- O(n^2) 算法和
- O(n) 算法

注意：这不是家庭作业。

Answer 1

• 在数组中搜索单个项目是O(N)
• O(N^2)如果您使用具有两个嵌套循环的简单算法，则在数组中搜索最长的递增数字^*

注意：这不是Java 特定的。

---

^*存在更快的算法来执行此搜索。

Answer 2

做一个O(n²)搜索算法是没有意义的。

要执行O(n)算法，只需搜索列表中的元素。

for(int i=0;i<array.length;i++)
  if(array[i]==search)
    return array[i];

Answer 3

好吧O(n)，这只是线性搜索；从头到尾遍历列表，直到遇到要搜索的内容。

奇怪的是你想要一个O(n²)算法......但是你可以做的是，在你的 for 循环的每次迭代中（在O(n)搜索中），休眠一个由数组长度定义的持续时间（Thread.sleep(array.length)）。“休眠”周期将O(n)线性依赖于数组的长度，并且整体线性搜索也将是O(n)，因此整个过程将是O(n²)。

---

O(n)

for (int i = 0 ; i < array.length ; i++) {
    if (array[i] == SOME_ELEMENT) {
        // ...
        break;
    }
 }    

O(n²)

for (int i = 0 ; i < array.length ; i++) {
    Thread.sleep(array.length);
    if (array[i] == SOME_ELEMENT) {
        // ...
        break;
    }
 }