問題複雜性

問題複雜性(problem complexity)計算機問題求解的重要概念之一是計算一個問題的所有算法中，時間複雜性最小的那個算法的複雜性(參見“計算複雜性”、“複雜性度量”、“時間複雜性”等).例如，在n個任意的整數中找出最大的數和最小的數，}3n/2-2]次比較運算是必須的，因此這個問題的複雜性是O(n).又如著名的梵塔問題，2" - 1次移動碟片是必須的，因此梵塔問題的複雜性是O(2").