我今天偶然发现了这个问题，并试图找到一个比0 (N)更好的解决方案，但无法想出一个。
搜索了SO，但没有找到这个问题。
有比O(n)更好的解决方案吗?还是这个问题没有比O(n)更好的解决方案?
我最初的想法是二分搜索，但你需要对它进行排序，这又是>n。我还想过对搜索元素可能所属的数组的一半应用快速排序，但我们最初进行n次比较，然后才丢弃另一半。我是做对了还是看错了方向?
我在c++中尝试解决方案，没有javascript的IndexOf()或c# Array.find()或LINQ的。
让它平行。将数组分成块并并行搜索。复杂度将是0 (n)，但运行时间将少得多。实际上它和no成正比。
你可以在c++中使用并行模式库
你是对的，最快的方法是简单地遍历数组并查找它。没有进一步的信息，你没有更好的办法。
除非你有一台量子计算机。
如果您只搜索一个元素一次，只需遍历它。没有比这更快的方法了。
如果您搜索多次，那么为它建立索引(或者排序，如果您愿意)并使以下搜索快速(log(n))是值得的。
通常，我们在一次迭代中检查数组的一个元素…它需要n次迭代才能完全循环遍历数组…因此，最坏情况下的时间复杂度为O(n)。
for(int i=0;i<s;i++){ // s = array size
if(arr[i] == n) // n = element to be searched
return i;
}
，但我的实验是在一次迭代中检查多个元素。假设每次迭代有5个元素。那么，在这种情况下，for循环就是这样的
// s = array size
// n = element to be searched
for(int i=0;i<s;i+=5){ // notice the increment in i here...
if(arr[i] == n)
return i;
/* check the next four indexes as well as if arr[i] is the last element of the array */
else if( arr[i+1] == n && i+1 < s)
return i+1;
else if(arr[i+2] == n && i+2 < s)
return i+2;
else if(arr[i+3] == n && i+3 < s)
return i+3;
else if(arr[i+4] == n && i+4 < s)
return i+4;
}
在这里，理论上时间复杂度应该是O(n/5)…
但是，当我执行程序时，取大小为1000000的数组，随机排列元素1到1000000，并计算两个循环对相同数组大小的不同测试用例所花费的时间…这些就是结果!
每次迭代一个元素
- 时间复杂度(以微秒为单位):4105 4180 4108 4115 4087 4137 4094 4089 4141 4167 4082 4084 41144118 4099
每次迭代5个元素
- 时间复杂度(以微秒为单位):1318 1382 1384 1297 1364 1289 1351 1617 1300 1289 1395 1385 1349 1329 1369
所以，正如我所看到的，它使时间复杂度发生了重大变化!
如果没有排序，则必须检查每个元素。
如果您不进行并行搜索，那么您可以将键插入到数组的末尾作为哨兵值，并且只进行'n'比较而不是进行2n比较。
详情请参考以下问题:使用哨兵线性搜索的意义是什么?
您可以使用这种方法搜索0(1)的元素。
创建一个MAP。当你插入一个值，然后为键赋值为'1'，并再次搜索它只是检查数组是否存在。
下面是代码:-
#include<bits/stdc++.h>
using namespace std;
int main(){
int n;
cin>>n;
map<int,int> map;
for(int i=0;i<n;i++){
int k;
cin>>k;
map[k]=1;
}
int num;
cin>>num;
if(map[num]){
cout<<"FOUND"<<endl;
}else{
cout<<"NOT FOUND"<<endl;
}
return 0;
}
Input:
5 // *no. of elements*
6 4 7 3 2 //*elements*
3 // *number to find*
输出:FOUND
这可以通过使用一些技巧来解决。在无序数组中，如果我们遍历它，在最坏情况下(当元素出现在最后一个索引时)的复杂度将是O(N)，其中N是数组的大小。这就是诀窍。首先检查最后一个索引，这样如果元素出现在最后一个索引(最坏的情况)，我们的代码将在0(1)内执行。然后是遍历并找到元素的代码。所以，现在最坏情况下的复杂度是0 (N-1)。
int findElement(int N, int arr[], int element){
if(arr[N]==element){
return i;
}
for(int i=0; i<N-1; i++){
if(arr[i]==element)
return i;
}
return -1;
}
在寻找比线性搜索更快的方法时，我偶然发现了"前后"线性搜索方法(https://medium.com/@insomniocode/search-algorithm-front-and-back- unsort-86d7a4bfc258)，我在几个实例上测试了它，结果证明它确实更快，但不是很明显。在我看来值得一试!
然而，还有另一种逻辑…
(偶数存储在偶数地址中)
-
首先检查搜索元素是奇数还是偶数
-
如果搜索元素为"偶数"，则只搜索偶数
- 可以通过以下逻辑跳过搜索中的一半元素
例如:
- 如果有100个元素以无序方式存储并搜索元素是98....因为搜索号是偶数…你可以跳过全部为奇数地址(因此跳过50个元素)，现在搜索完成仅限其余50个偶数地址....
您可以将元素划分并并行搜索或使用"pivot key"排序到剩余的50个元素或任何其他搜索方法
在快速排序过程中使用分区方法的算法效率如何?
-
在列表中随机选择一些值(我们称之为v)
-
将整个列表划分为2部分。
-
重复步骤2、3，直到确定元素是否存在。
我不确定以上算法的复杂度，但看起来肯定比快速排序算法的复杂度要小:(n log n).
给定下面的数组，你可以做并行搜索。
const array = [1, 2, 3, 4, 5, 6, 7, 3];
const search = 3;
for (let i = 0; i < array.length; i++) {
if (array[i] === search) {
console.log(i);
break;
}
if (typeof array[i + 1] !== "undefined") {
if (array[i + 1] === search) {
console.log(i + 1);
break;
}
if (typeof array[i + 2] !== "undefined") {
if (array[i + 2] === search) {
console.log(i + 2);
break;
}
if (typeof array[i + 3] !== "undefined") {
if (array[i + 3] === search) {
console.log(i + 3);
break;
}
if (typeof array[i + 4] !== "undefined") {
if (array[i + 4] === search) {
console.log(i + 4);
break;
}
if (typeof array[i + 5] !== "undefined") {
if (array[i + 5] === search) {
console.log(i + 5);
break;
}
if (typeof array[i + 6] !== "undefined") {
if (array[i + 6] === search) {
console.log(i + 6);
break;
}
if (typeof array[i + 7] !== "undefined") {
if (array[i + 7] === search) {
console.log(i + 7);
break;
}
}
}
}
}
}
}
}
}
有可能使你的程序运行得比O(n)快。
首先使用归并排序算法对数组进行排序，然后使用二分查找来查找元素。两种算法的运行时间都是O(log_2(n))。把这两个复杂度加在一起，你得到2*log_2(n)，也就是O(log_2(n))和见证物C = 2。