1. 时间复杂度和空间复杂度的计算（1）

1. 什么是时间复杂度和空间复杂度？

1.1 算法效率

**算法效率分析分为两种：第一种是时间效率，第二种是空间效率。**时间效率被称为时间复杂度，而空间效率被称为空间复杂度。时间复杂度主要衡量一个算法的运行速度，空间复杂度主要衡量一个算法所需要的额外空间

1.2 时间复杂度的概念

定义：在计算机科学中，算法的时间复杂度是一个函数，定量描述了该算法的运行时间。算法中的基本操作的执行次数就是算法的时间复杂度

1.3 空间复杂度的概念

空间复杂度是对一个算法在运行过程中临时占用存储空间大小的量度，使用大O渐进表示法

2. 如何计算时间复杂度

2.2 大O的渐进表示法

实际我们计算时间复杂度时候，并不一定要计算精确的执行次数，而只需要大概执行次数，使用大O阶方法

推导大O阶方法：

1. 用常数1取代运行时间中的所以加法常数
2. 再修改后的运行次数函数中，只保留最高阶项
3. 如果最高阶存在且不是1，则去除与中国项目相乘的常数。得到的结果就是大O阶

实例1：

//请计算一下Func1基本操作执行了多少次？
void Func1(int N)
{
	int c=0;
    for(int i=0;i<N;++i)
    {
		for(int j=0;j<M;++j)
        {
			++c;
        }
    }
    for(int k=0;k<2*N;k++)
    {
		++c;
    }
    int M=10;
    while(M--)
    {
        ++c;
    }
    printf("%d\n",c);
}

准确次数：N*N+2 * N +10

F(N) = N^2+2*N+10 (随着N的增大，N^2对结果的影响最大)

根据例子分析，时间复杂度可以分为三个部分。

1. 两个for循环的嵌套 —— O(N^2)
2. 单独的for循环 —— O(N*2)
3. while的递减 —— O(1)

因此该例子的时间复杂度就为O(N^2)

注：时间复杂度就是一个估算，看表达式中影响最大的那一项

实例2：

//计算Func2的时间复杂度
void Func2()
{
	int c=0;
    for(int k=0;k<M;++k)
    {
		++c;
    }
    for(int k=0;k<N;++k)
    {
		++c;
    }
    printf("%d\n",c);
}

通过分析，我们发现题目没有给出M和N的值 ，因此该例子的时间复杂度就为O(N+M)

如果给了具体条件就比较M和N的大小 ，来得出时间复杂度

实例3

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

时间复杂度为 O(1)

如果是确定的常数次，时间复杂度都是 O(1)

实例4

//计算strchr的时间复杂度
const char*strchr(const char*str,char character)
{
	while(*str != '\0')
    {
		if(*str==character)
            return str;
        ++str;
    }
    return null;
}

如果字符串长度只有1 那结果就是 O(1)

如果字符串长度为N 那结果就是 O(N）

得看最坏情况所以应该为 O(N)

补充：

有些 算法的时间复杂度存在最好、平均和最坏的情况：

• 最坏情况：任意输入规模的最大运行次数（上界）
• 平均情况：任意输入规模的期望运行次数
• 最好情况：任意输入规模的最小运行次数（下界）

例如：在一个长度为N的数组中搜索一个数据x

最好情况：1次找到

最坏情况：N次找到

平均情况：N/2次找到

在实践中一般情况关注的是算法的最坏运行情况，所以数组中搜素数据时间复杂度为O(N)

实例5

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

冒泡排序的时间复杂度分析：

第一趟冒泡：N

第二趟冒泡：N-1

第三趟冒泡：N-2

……

第N趟冒泡：1

利用等差数列公式计算： (N+1)*N/2 ————准确的次数

而影响最大的是 N^2

即时间复杂度为O(N^2)

实例6

//计算BinarySearch的时间复杂度
int BinarySearch(int*a,int n,int x)
{
	assert(a);
	int begin=0;
	int end=n;
	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(1) ， 即一次就找到

假设找了X次

1 * 2 * 2…* 2=N

2^X = N

X = log N (log的底数为2)

实例7

//计算阶乘递归Factorial的时间复杂度
long long Factorial(size_t N)
{
	return N < 2 ? N: Factorial(N-1)*N;
}

递归调用了N次，每次递归运算多少次 ——> O(1)

整体就是 O(N)

注： 常见的时间复杂度：O(N^2) O(logN) O(1)