如何計算簡單搜索的複雜度

Question

我有一個包含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的最後一個元素或不匹配）的複雜性？

Answer 1

時間複雜度：

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

所以，當你搜索你的數組，你實際做ñ比較。將數組中的每個元素與輸入元素進行比較。因此，在這種情況下：

最佳情況：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個元素的存在在數組中。