时间复杂度

目录

​编辑

复杂度的概念：

时间复杂度的概念：

大O的渐进表示法：

推到大O渐进表示法：

大O渐进表示法的关系和大小：

其他的代码的时间复杂度： 

 在一个长度为N数组中搜索一个数据X：

交换位置（冒泡排序）： 

O(log N):

 二分查找：

递归： 

计算斐波那契递归的时间复杂度：

---

 

复杂度的概念：

算法在编写成可执行程序后，运行时需要耗费时间资源和空间(内存)资源 。因此衡量一个算法的好坏，一般 是从时间和空间两个维度来衡量的，即时间复杂度和空间复杂度。

时间复杂度主要衡量一个算法的运行快慢，而空间复杂度主要衡量一个算法运行所需要的额外空间。

时间复杂度的概念：

在计算机科学中，算法的时间复杂度是一个函数，它定量描述了该算法的运行时间。

一个算法所花费的时间与其中语句的执行次数成正比例，算法中的基本操作的执行次数，为算法 的时间复杂度。

找到某条基本语句与问题规模N之间的数学表达式，就是算出了该算法的时间复杂度。 

而这种数学表达式通常是使用大O的渐进表示法。 

大O的渐进表示法：

大O符号（Big O notation）：是用于描述函数渐进行为的数学符号。

推到大O渐进表示法：

//请计算一下Func1中++count语句总共执行了多少次？
 
 
void Func1(int N)
{
    int count = 0;
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            ++count;
        }
    }
    for (int k = 0; k < 2 * N; ++k)
    {
        ++count;
    }
    int M = 10;
    while (M--)
    {
        ++count;
    }
    printf("%d\n", count);
}

Func1 执行的基本操作次数 ：

• N = 10 F(N) = 130
• N = 100 F(N) = 10210
• N = 1000 F(N) = 1002010 

分析，由于此处的基本操作是三个循环：且因为时间复杂度的本质是算法中的基本操作的执行次数。

所以，本代码的时间复杂度是  2*N+N*N+10

• 但是按照大O渐进表示法的规则，取数学表达式中的最大一项，且若最大一项是常数，则用1表达，若最大一项有系数，则删除系数。

所以以上代码用大O渐进表示法表示为  O（N^2） 

 
//嵌套循环
    for (int i = 0; i < N; ++i)
    {
        for (int j = 0; j < N; ++j)
        {
            ++count;
        }
    }
 
//普通循环1：
 
for (int k = 0; k < 2 * N; ++k)
    {
        ++count;
    }
 
//普通循环2：
 int M = 10;
    while (M--)
    {
        ++count;
    }

大O渐进表示法的关系和大小：

一般来说，大O渐进表示法的表达式是：O（N）、O（N^2）、O（1）

• 其中的N表达的是某一算法中的基本操作的运行次数。
• 1也表示一种次数，但不是表示运行一次，而是使用数学关系式计算出，时间复杂度最后是一个常数，又因为计算机的cpu功能，处理和运行一个时间复杂度是常数的代码，它的运行和处理速度是非常快的，哪怕这个常数是一亿。 
• 需要注意，O(N)、O(N^2)、O(1)中，运行性能和速度的大小关系是：O(1) > O(N) > O(N^2)

注意：这个常数必须要在类型（如int、long long、long）的范围内，不然会溢出。 

其他的代码的时间复杂度： 

 在一个长度为N数组中搜索一个数据X：

const char * strchr ( const char * str, int character )
{
 
   while(*str)
  {
    if(*str == character)
    return str;
  }
 
 ++str;
  
 
}

根据时间复杂度的本质，"算法中的基本操作的执行次数，就是时间复杂度"，而本代码中的多次运行的操作是移动，移动指针查找是数组中的元素是否是我们需要的。

所以从指针开始遍历数组，直到找到需要的元素，这一段查找确认的次数就是时间复杂度。

而找到元素，这个是难以确认的，我们不知道元素是否在哪，所以这里有一种不确定性。

而对于这种不确定性，我们选择了一种最坏的结果，那就是没有找到元素，而没有找到元素就是要先将数组用指针遍历一遍，所以，这个代码的时间复杂度就转化为了：要把指针移动几次，才能将数组遍历一遍。

而数组的长度是N，那么指针则需要遍历N次，才能将数组遍历完一遍。 

交换位置（冒泡排序）： 

void BubbleSort(int* a, int n)
{
 
 assert(a);
 
 for (size_t end = n; end > 0; --end)//每次交换所需要的趟数
 {
   int exchange = 0;
   for (size_t i = 1; i < end; ++i)
   {
     if (a[i-1] > a[i])
     {
       Swap(&a[i-1], &a[i]);
       exchange = 1;
     }
   }
   if (exchange == 0)
   break;
 }
 
}

 根据时间复杂度的本质，"算法中的基本操作的执行次数，就是时间复杂度"，而本代码中的多次运行的操作是每次交换所需要的趟数！

注意该代码中的交换是使用了调用函数，所以不需要算上交换的次数。

• 从我们的初步运算，得知交换的趟数是N*（N-1+1-1）/2 ，最后算出(N^2)/2
• 按照大O渐进法，得到该代码的时间复杂度是O（N^2） 

O(log N):

void fun(int n) {
  int i=l;
  while(i<=n)
    i=i*2;
}

• 此函数有一个循环，但是循环没有被执行n次，因为 i每次都是 2 倍进行递增，所以循环只会被执行log2(n)次。 

 二分查找：

int BinarySearch(int* a, int n, int x)
{
	assert(a);
	int begin = 0;
	int end = n - 1;
	// [begin, end]：begin和end是左闭右闭区间，因此有=号
	while (begin <= end)
	{
		int mid = begin + ((end - begin) >> 1);
		if (a[mid] < x)
			begin = mid + 1;
		else if (a[mid] > x)
			end = mid - 1;
		else
			return mid;
	}
	return -1;
}

 

• 如图所示，我们再查找指定数字的时候并不是将整个数组（大小为N）遍历了一遍，而是直接再数组中间（N/2）的位置进行对比。
• 而最坏的情况就是，N/2 /2 /2 /2 ……直到中间只有一个数字位置
• 而将x作为查找到数字的次数，进行轮番的乘2，最后得出的结构就如上图所示 log 2 N 次
• 所以大O渐进法就是O（log 2 N）2可以省略，所以便是 O（log N） 

递归： 

  int f ( unsigned int n ) {
    if (n == 0 || n==1) 
      return 1;
    else 
      return n * f(n-1);
  }

•  关于递归，因为我们时间复杂度的本质是某一个基本操作运行的次数累加，所以再递归中，我们是运行了N次的n*f（n-1）——n变成1位置
• 所以，上诉代码的时间复杂度是O（N）

计算斐波那契递归的时间复杂度：

long long Fib(size_t N)
{
 if(N < 3)
 return 1;
 
 return Fib(N-1) + Fib(N-2);
}

• 再斐波那契额数列中，一个数是由前两个数字组成的

 

如上图所示，每一次的调用，都会产生新的分支，而新的分支又会再产生另外的新分支

而时间复杂度取决于某一个操作的运行次数。

再最开始的调用中，会分为两个部分，而每个部分又会产生全新的两个部分，直到结束。

所以这里需要要运用的是等差数列的和公式，进行运算。

以此得到的最后结果是O（N） 

 

---