时间空间复杂度基础

• 时间空间复杂度用大写的O来表示（例如：O(1),O(n²)等等）。在我们进行时间空间复杂度的计算时，我们不需要明确计算，常数项和低增长项都可以忽略，只需要估算并且保留最高增长项。
• 时间复杂度用来衡量一个算法的执行效率，时空复杂度用来衡量算法的内存消耗，他们都是越小越好。

时间空间复杂度：

怎样进行估算？ 现在可以进行简单的理解：时间复杂度大部分情况下就是看for循环的最大嵌套层数

总执行次数T(n)是不是常数项：

• 是：时间复杂度为O(1)
• 否：时间复杂度为O(保留最高增长项，并去除最高次项的系数)

示例：

时间复杂度O(1) 空间复杂度：O(1)

void function(void)
{
	printf("H");
	printf("e");
	printf("l");
	printf("l");
	printf("o");
}

时间复杂度O(n) 空间复杂度：O(1)

void function(int n)
{
	for (int i = 0; i < n; i ++ ) {
		printf("1");
	}
}

时间复杂度O(n²) 空间复杂度：O(1)

void function(int n)
{
	for (int i = 0; i < n; i ++ ) {
		for (int j = 0; j < n; j ++ ) {
			printf("1");
		}
	}
}

在函数内，最里面的循环执行为n+1次，约等于n次。外面的循环约等于运行了n次。所以运行时间为：O(n²) 有几层循环嵌套就是n的多少次方

时间复杂度O(n) 空间复杂度：O(n)

void function(int n) {
    vector<int> nums(n);
}

这个函数中创建了一个大小为 n 的数组，所以空间复杂度是 O(n)。

时间复杂度不仅仅体现在我们所看到的for循环内，每一行代码都可能对计算时间复杂度做出更改。所以要了解编程语言提供的常用数据结构实现原理，这是准确分析复杂度的基础。

时间复杂度排序：

O(1) < O(logn) < O(n) < O(nlogn) < O(n²) < O(n^3) < O(2^n)