算法复杂度关注的是每个函数随着容器中条目数量的增长有多快(或多慢)。例如，在QlinkedList的中间插入一个项是一种非常快的操作，不管QlinkedList中存储了多少项。另一方面，如果QVector包含许多项，则在QVector中间插入项可能非常昂贵，因为必须将一半的项移动到内存中的一个位置。
为了描述算法复杂度，我们使用以下术语，基于“big Oh”符号:
- Constant time: O(1). 如果不管容器中有多少项，函数都需要相同的时间，则函数被称为在常数时间内运行。 一个例子是QlinkedList::insert()。
- Logarithmic time: O(log n). 以对数时间运行的函数是其运行时间与容器中项目数的对数成正比的函数。 一个例子是qBinaryFind()。
- Linear time: O(n). 以线性时间运行的函数执行的时间与容器中存储的项数成正比。 一个例子是QVector::insert()。
- Linear-logarithmic time: O(n log n). 以线性-对数时间运行的函数比线性时间函数渐进地慢，但比二次时间函数快。
- Quadratic time: O(n²). 二次时间函数的执行时间与容器中存储的项数的平方成正比。
下表总结了Qt顺序容器类的算法复杂度:
| Index lookup(索引查找) | Insertion(插入) | Prepending(从前面添加) | Appending(从后面追加) | |
| QlinkedList | O(n) | O(1) | O(1) | O(1) |
| QList | O(1) | O(n) | Amort. O(1) | Amort. O(1) |
| QVector | O(1) | O(n) | O(n) | Amort. O(1) |
表中"Amort "代表"平摊行为" 例如,“Amort. O(1)”意味着如果你只调用一次函数，你可能会得到O(n)的行为，但如果你调用它多次(例如，n次)，平均行为将是O(1)。
下表总结了Qt关联容器和集合的算法复杂度:
| Key lookup(key查找) | Insertion(插入) | |||
| Average(平均) | Worst case(最坏情况) | Average(平均) | Worst case(最坏情况) | |
| QMap | O(log n) | O(log n) | O(log n) | O(log n) |
| QMultiMap | O(log n) | O(log n) | O(log n) | O(log n) |
| QHash | Amort. O(1) | O(n) | Amort. O(1) | O(n) |
| QSet | Amort. O(1) | O(n) | Amort. O(1) | O(n) |
使用QVector、QHash和QSet，附加项的性能被平摊到O(log n)。在插入项之前，通过调用QVector::reserve()、QHash::reserve()或QSet::reserve()可以将附加项的期望数量降至O(1)。 下一节将更深入地讨论这个主题。
