0

我有一个包含 n 个元素的数组。现在我需要搜索一个元素 x。这是程序

int x[100],i,s;
cout<<"Enter how many number of element you have";
cin>>n;
for(i=0;i<n;i++)
{
  cin>>x[i];
}
cout<<"Enter element which you want to search";
cin>>s;
for(i=0;i<n;i++)
{
  if(x[i]==s)
  {
   cout<<"Item found in position"<<i;
   break;
  }
}

这个程序的时间和空间复杂度是多少？

Space: 
x[100] = 200 bytes
n      = 1 byte 
s      = 1 byte
==================
Total  = 202 bytes

这是对的吗？

时间复杂度：请帮我弄清楚

最佳情况（如果 x 匹配 n 的第一个元素）复杂性？最坏的情况（如果 x 匹配 n 的最后一个元素或不匹配）复杂性？

4

1 回答 1

0

时间复杂度：

Time complexity is nothing but number of comparisons done by computer in your code.

因此，当您搜索数组时，您实际上会进行 n 次比较。将数组中的每个元素与您的输入元素进行比较。所以，在这种情况下：

最佳情况：O(1) - 在第一次比较中找到元素。

最坏情况：O(n) - 意味着您必须搜索所有元素，并且您在数组的最后一个位置找到了该元素。

空间复杂度：

Normally, this is seen in terms of numbers of elements in the array rather 
then the total size taken by these elements. This is done because size of data 
types differ on various architectures but number of elements is dependent on the 
problem and not the machine.

因此，在您的情况下：

空间复杂度 = "n"..因为数组中存在 n 个元素。

于 2013-10-20T03:02:57.023 回答