问题复杂性

问题复杂性(problem complexity)计算机问题求解的重要概念之一。是计算一个问题的所有算法中，时间复杂性最小的那个算法的复杂性(参见“计算复杂性”、“复杂性度量”、“时间复杂性”等).例如，在n个任意的整数中找出最大的数和最小的数，}3n/2-2]次比较运算是必须的，因此这个问题的复杂性是O(n).又如著名的梵塔问题，2" - 1次移动盘片是必须的，因此梵塔问题的复杂性是O(2").