“复杂度”描述了执行操作所需的时间,又快到慢依次为:
(1)编译时间;
(2)固定时间;
(3)线性时间。
若复杂度为编译时间:操作将在编译时执行,执行时间为0;
若复杂度为固定时间:操作发生在运行时,但是独立于对象中的元素数目(不受元素个数影响);
若复杂度为线性时间:此时,时间与元素数目成正比。
例子:
为何list容器和deque容器定义了push_front()函数(把元素移动到首位),而vertor没有?
对于vector容器,要实现把一个新值放到所有元素最前面,那么就需要所有元素向后移动一位,从而腾出空间。这种操作的复杂度是“线性时间”,十分糟糕。而对于list和deque,属于“固定时间”。因此,“固定时间”复杂度的操作才会被实现。