複雜性度量

複雜性度量(complexity measure)計算複雜性的衡量標準(參見“算法分析”、“計算複雜性理論”、“計算複雜性”等)。這種衡量標準不能表示為絕對的數量大小,而應表示為問題大小n的一個函式。

基本介紹

  • 中文名:複雜性度量
  • 外文名:complexity measure
例如對一個問題的某個算法所消耗的時間的度量,不應依賴於計算工具的計算速度,而應將算法的主要運算次數表示為n的函式.在用普通的算法計算兩個n階方陣的乘積的過程中,其運算次數約為2n3+2nz+n,它是n的三階多項式,忽略低次項後,可寫為O(n3 ).這裡0(n3)表示是與n3同階的一個量,O可以認為是與n無關的某個常量.

相關詞條

熱門詞條

聯絡我們