时间复杂度（常数循环、strchr、冒泡排序、二分查找）

1.1常数循环

//计算复杂度
void Func4(int k)
{
  int count=0;
  for(intk=0;k<100;++k)
  {
    ++count;
  }
  printf("%d\n",count);
}

时间复杂度为：O(1)  

注：O(1)不是代表算法只能运行一次，是常数次

1.2strchr的时间复杂度

//计算strchar的时间复杂度
const char* strchr(const char* str,int character)

strchr主要用来查找字符串中的某个字符

while(*str)
{
  if(*str==character)
    return str;
  else
    ++str;
}

假设在一串字符“hello world”中分别查找h w d 三个字符

所以也分为三种情况：最好    平均     最坏

                                O(1)   O(N/2)  O(N)

注：当一个算法随着输入的不同，时间复杂度做悲观的预期，看最坏的情况

所以该算法的时间复杂度为O(N)

1.3冒泡排序的时间复杂度

//计算BubbleSort的时间复杂度？
void BubbleSort(int* a,int n)
{
  assert(a);
  for(size_t end=n;end>0;--end)
  {
    int exchange=0;
    for(size_t=1;i<end;++i)
    {
      if(a[i-1]>a[i])
      {
        Swap(&a[i-1],&a[i]);
        exchange=1;
      }
    }
    if(exchange==0)
      break;
  }
}

精确：F(N)=N*(N-1)/2

时间复杂度：O(N^2)

1.4二分查找

//计算BinarySearch的时间复杂度
int BinarySearch(int* a,int n,int x)
{
  assert(a);
  int begin=0;
  int end=n-1;
  while(begin<end)
  {
    int mid=begin+((end-begin)>>1);
    if(a[mid]<x)
      begin=mid+1;
    else if(a[mid]>x)
      end=mid;
    else
      return mid;
  }
  return -1;
}

时间复杂度：O(log₂N)

简单介绍一下二分查找的威力之大：

N个数中查找：                大概查找次数：

• 1000                                  10
• 100万                                 20  
• 10亿 30

解释：2^t=N      2¹⁰=1024   2²⁰=2¹⁰*2¹⁰大概就等于十万