算法1.5--顺序搜索算法(SeqSearch)

如果数据规模为N,即list长度为N,显然,最坏的时间复杂度W(N) = N.最好的当然是在第一个,B(N)=1

 

设X为要搜索的元素,X在list中,则有N种情况,X=list[1], X=list[2], ... X=list[n],X不在List中的情况为X=out_list.

 

假设X在list的中的概率为q, 则不在list中的概率为 1-q.

同时假设X在list中等于任何一个元素是等可能的,即 P(X=list[i]) = q/N

则平均复杂度为

A(N) = ｛从i=1到i=N累加｝P(X=list[i-1]) * i  +  P(X=out_list)*N

     = (q + 2*q + ... +N*q)/N + (1-q)/N

     = q(N+1)/2 +(1-q)/N

     = q/2 + N -qN/2

 

q=1,即X在list中的平均复杂度为(N+1)/2

 

#include
#include
#include

#define MAX_LENGTH 1000

/*Show usage*/
void usage(char * prog)
{
        printf("%s Usage:\n", prog);
        printf("%s \n", prog);
}

/*Generate and initialize the list*/
int * generate_list(int count)
{

        int i;
        int * list;
        list = (int *)malloc(count*sizeof(int));
        if(list == NULL)
        {
                perror("malloc");
                return NULL;
        }

        /*Initialize the list with integers less than 100*/
        srandom((unsigned int)time(NULL));
        for (i  = 0; i < count ; i ++)
                list[i] = random()%100;

        return list;
}

/*Generate a element to search*/
int rand_to_search(int * list, int length)
{
        int s;
        s = random()%100;
        return s;
}

/*SeqSearch Algorithm*/
int seqsearch(int * list, int length, int to_search)
{
        int i = 0;
        while((i < length) && (list[i] != to_search) ) i ++;
        return i;
}

int main(int argc, char * argv[])
{
        int length, i;
        int * list = NULL;
        int to_search, place;

        /*Deal with the arguments*/
        if(argc != 2)
        {
                usage(argv[0]);
                exit(127);
        }

        length = atoi(argv[1]);
        if(!length || length > MAX_LENGTH)
        {
                usage(argv[0]);
                exit(129);
        }

        list = generate_list(length);
        if(list == NULL)
                exit(128);
        else
        {
                for(i = 0; i < length; i ++)
                        printf("%d ", list[i]);
                printf("\n");
                to_search = rand_to_search(list, length);
                printf("Try to search: %d\n", to_search);
                place = seqsearch(list, length, to_search);
                if(place >= length)
                        printf("%d is not in the list!\n", to_search);
                else
                        printf("Position: %d\n", place + 1);
        }
        free(list);
        return 1;
}