计算复杂性问题的大小和复杂性的度量和可计算性一样，复杂性总是对于一个特定的问题类来讨论的，它包括无穷多个个别问题，有大有小
例如，对矩阵乘法这样一个问题类，相对地说，100 阶矩阵相乘是个大问题，而二阶矩阵相乘就是个小问题
可以把矩阵的阶 n 作为衡量问题大小的尺度
又如在图论问题中，可以把图的顶点数 n 作为衡量问题大小的尺度
一个个别问题在计算之前，总要用某种方式加以编码，这个编码的长度 n 就是衡量问题大小的尺度
当给定一个算法以后，计算大小为 n
的问题所需要的时间、空间等就可以表示为 n 的函数
这个函数就可作为该算法的时间或空间复杂性的度量
严格地讲，是这个特定的问题类在某一特定计算模型中某一特定算法的复杂性之度量
当要解决的问题越来越大时，时间、空间等资源耗费将以什么样的速率增长，即当 n 趋向于无穷大时，这个函数的性状如何，增长的阶是什么，这就是计算复杂性理论所要研究的主要问题
以上内容由大学时代综合整理自互联网，实际情况请以官方资料为准。
