运行时间中的对数

如果一个算法用常数时间(O(1))将问题的大小消减为某一部分的（通常1/2），那么该算法就是O（logN）.另一方面，如果使用常数时间只是把问题减少一个常数，那么该算法就是O(N).

对分查找：

给定一个整数X和整数后者已经预先排序并在内存中，求使得的下标i,如果X不在数据中，则返回i=-1.明显的算法是从左到右扫描数据，其运行花费的线性时间。然而，这个算法没有用到该表已经排序的事实，这就使得算法不是很好。一个好的策略是验证X是否居中的元素。如果是，则答案就找到了。如果X小于居中元素，那么我们可以应用同样的策略于居中元素左侧已经排序的子序列；同理，如果X大于居中元素，那么我们检查右半部分。

      #include <stdio.h>
      #include <stdlib.h>
      int BinarySearch(const int A[],int X,int N)
      {
     	int Low,Mid,High;
      	Low=0;
      	High=N-1;
     	while(Low<=High)
      	{
      		Mid=(Low+High)/2;
     		printf("(Low+High)/2;%d,Low %d,High %d\n",Mid,Low,High);
     		if(A[Mid]<X)
      		{
      			Low=Mid+1;
     			printf("Low;%d\n",Low);
      		}
     		else
      		{
     			if(A[Mid]>X)
      			{
      				High=Mid-1;
     				printf("High;%d\n",High);
      			}
     			else
      			{
     				printf("Mid;%d\n",Mid);
     				return Mid;
      			}
      		}
      	}
     	return -1;
      }
      int main()
      {
     	int number[]={1,4,10,15,16};
     	int data=0;
     	printf("start ....\n");
      	data=BinarySearch(number,4,5);
     	printf("下标是:%d\n",data);
     	exit(0);
      }
  
 

运行

      start ....
      (Low+High)/2;2,Low 0,High 4
      High;1
      (Low+High)/2;0,Low 0,High 1
      Low;1
      (Low+High)/2;1,Low 1,High 1
      Mid;1
      下标是:1
  
 

欧几里德算法

两个整数的最大公因数是同时整除二者的最大整数。

      #include <stdio.h>
      #include <stdlib.h>
      int Gcd(unsigned int M,unsigned int N)
      {
     	unsigned int Rem;
     	while(N>0)
      	{
      		Rem=M%N;
      		M=N;
      		N=Rem;
      	}
     	return M;
      }
      int main()
      {
     	int number[]={1,4,10,15,16};
     	int data=0;
     	printf("start ....\n");
      	data=Gcd(4,5);
     	printf("Gcd:%d\n",data);
     	exit(0);
      }
  
 

运算

      start ....
      Gcd:1
  
 

文章来源: xintiaobao.blog.csdn.net，作者：心跳包，版权归原作者所有，如需转载，请联系作者。

原文链接：xintiaobao.blog.csdn.net/article/details/89485952