算法的时间复杂度和内存复杂度的定义是什么?

Question

寻找对任何算法的时间和内存复杂性的一般理解。

Answer 1

当我们讨论算法的事物复杂性时，我们讨论的是当输入的大小增加时，事物的一般函数集。

对于时间，这是很明显的，它是执行一个算法所需的时间(通常是"操作的次数")。

对于内存，我们通常指的是算法所需的额外内存。这包括"显式临时变量"、"堆栈"等内容。和其他人。

为了复杂性，我们经常使用"big-O"符号。一般形式是f(n) O(g(n))，意思是我们得到的(确切的)函数是一个集合的一部分，使得存在一个m，使得所有k≥m，和一个c，使得f(k)≤c * g(k)。