我在下面写的线性搜索c代码的时间复杂度是多少?我的代码是好是坏

Question

//线性搜索

#include<stdio.h>

void main()
{
    int a[]={1,2,3,4,5,6,7,8,9,10};
    int key;
    int v;
    printf("Insert the number you want to find in the list::n");
    scanf("%d",&v);


    for(int i=0;i<=10;i++)
    {
        if(a[i]==v){
            key=i;
       break;
        }else{
          key=-1;
        }
    }  
      if(key>=0){
          printf("Number found at possition %dnnn",key);
    }
    else{
        printf("Sorry Not found in the listnnn");
    }
    printf("A programme by Soumya Darshan Rauth");
}

Answer 1

您的程序以线性时间运行，适用于较小的数组。对于任意输入，您的程序是最优的。尽管我不认为每次找不到所需值时都需要设置key=-1。

key = -1; for(int i=0;i<=10;i++) { if(a[i]==v){ key=i; break; } }


即使这样也会很好。

Answer 2

线性搜索具有线性时间复杂度O（n），但对于像您这样的固定大小的数组，可以说它具有恒定的时间复杂度奥（1）。

Answer 3

正如大家所说，它是O（n），但排序数组可以在O（log2（n））中搜索，因此在算法上它不是可以做的最好的

此外，在C上，它是脆弱的。它对10个数字不起作用，对11以外的任何其他数字都会失败。

通常，我们要么有一个名称，它是数组中元素的实际数量（我将使用旧式C，它可以处理任何事情：

void main()
{
#define MAX_A (10)
    int a[MAX_A]={1,2,3,4,5,6,7,8,9,10};
       // deleted some stuff
    for(int i=0; i<MAX_A; i++)
    {
        if(a[i]==v){
            key=i;
            break;
        }else{
            key=-1;
        }
    }  

或者我们用这个稍微奇怪的sizeof计算来计算阵列的正确大小

void main()
{
    int a[MAX_A]={1,2,3,4,5,6,7,8,9,10};
       // deleted some stuff
    for(int i=0; i<sizeof(a)/sizeof(a[0]); i++)
    {
        if(a[i]==v){
            key=i;
            break;
        }else{
            key=-1;
        }
    }  

其总是阵列的大小。

你可以写一个更直接的循环，例如

for (key=0; a[key]!= v && key<sizeof(a)/sizeof(a[0]); key++)

然后，匹配测试更改为key < sizeof(a)/sizeof(a[0])

Answer 4

每次在数组中找不到值时，都会操作变量'key'。

你可以做的一个改进是将关键变量初始化为-1，并从循环中删除"else"代码块。

Answer 5

线性搜索的复杂性总是O（n）。

通常，main方法应该始终有一个整数作为返回类型（0表示成功，其他一切都表示发生了错误）。此外，main方法接受两个参数，即参数数量和作为char数组的参数（int argc，char*argv[]）。如果不需要参数，最好在括号（int main（void））之间写"void"。for循环中的break语句通常被认为是不好的做法，因为循环何时/是否结束并不明显。在您的情况下，while循环将提高可读性。while循环看起来像这样：

while (i < 10 && a[i] != v) {
    i++;
}
if (i >= 10) { ... } // not found
else { ... } // found at position i