时间复杂度与空间复杂度

时间复杂度：主要衡量的是一个算法的运行速度。

空间复杂度：主要衡量一个算法所需要的额外空间。

在计算机发展的早期，计算机的存储容量很小，所以对空间复杂度很是在乎。但是随着计算机行业的迅速发展，计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。

大O的渐进表示法规则

时间复杂度和空间复杂度一般都使用大O的渐进表示法进行表示，大O的渐进表示法规则如下：

1、所有常数都用常数1表示。
2、只保留最高阶项。
3、如果最高阶项存在且不是1，则去除与这个项的系数，得到的结果就是大O阶。

时间复杂度：基本操作的执行次数。

例子：

//计算Func1的时间复杂度
void Func1(int N)
{
    int count = 0;
    for (int i = 0; i < 2 * N; i++)
    {
        for (int j = 0; j < 2 * N; j++)
        {
            count++;
        }
    }
    for (int k = 0; k < 2 * N; k++)
    {
        count++;
    }
}

Func1函数执行了一个嵌套的for循环（共执行了4 * N2次），又执行了一个单独的for循环（共执行了2 * N次），所以Func1函数的时间复杂度为：T(N) = 4 * N2 + 2 * N 。

根据大O的渐进表示法，只保留最高阶项（即4 * N2），去除最高项的系数后（即N2），就是最终结果。所以，用大O的渐进表示法表示Func1函数的时间复杂度为：O(N2) 。

//计算Func2的时间复杂度
void Func2(int N)
{
	int count = 0;
	for (int k = 0; k < 100; k++)
	{
		++count;
	}
}

Func2函数内部执行了一个for循环（共100次），Func2函数内语句的执行次数不会随着传入的变量N的改变而改变，即执行的次数为常数次。Func2函数的时间复杂度为T(N) = 100 。

根据大O的渐进表示法，所有的常数都用常数1来表示，所以，用大O的渐进表示法表示Func2函数的时间复杂度为：O(1) 。

注意：在刷题时看到题目要求时间复杂度为O(1)，并不是要求函数内部不能含有循环，而是要求循环的次数为常数次。
空间复杂度：算的是变量的个数

//计算冒泡排序函数的空间复杂度
void BubbleSort(int* a, int N)
{
	assert(a);
	for (int i = 0; i < N; i++)
	{
		int exchange = 0;
		for (int j = 0; j < N - 1 - i; j++)
		{
			if (a[j]>a[j + 1])
			{
				int tmp = a[j];
				a[j] = a[j + 1];
				a[j + 1] = tmp;
				exchange = 1;
			}
		}
		if (exchange == 0)
			break;
	}
}

冒泡排序函数中使用了常数个额外空间（即常数个变量），所以用大O的渐进表示法表示冒泡排序函数的空间复杂度为O(1) 。