运行时间中的对数

如果一个算法用常数时间(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