|
===================================== 〔語彙分解〕的な部分一致の検索結果は以下の通りです。 ・ 回 ： [かい] 【名詞】 1. counter for occurrences ・ 回路 ： [かいろ] 【名詞】 1. circuit (electric) ・ 路 ： [ろ] 【名詞】 1. road 2. street 3. path ・ 計 ： [けい] 1. (n,n-suf) plan ・ 計算 ： [けいさん] 1. (n,vs) (1) calculation 2. reckoning 3. count 4. (2) forecast ・ 量 ： [りょう] 1. amount 2. volume 3. portion (of food) 4. basal metabolic rate, quantity
回路計算量（英: Circuit complexity）とは、計算複雑性理論において、ブール関数をその計算に要する計算資源の量によって分類することを指す。回路計算量では、それらの資源量は論理回路の大きさや深さで表される。 == 概要 == 入力が ''n'' ビットの論理回路は有向非環状グラフであり、各ノード（回路計算量の場合、「ゲート」と呼ぶ）は、入次数 0 の入力ノード（''n''個の入力ビットのいずれかに対応）か、ANDゲート、ORゲート、NOTゲートである。これらのゲートのいずれかが出力ゲートとなる。このような回路が ''n'' 個の入力の関数を計算する。回路の大きさは、全ゲート数と、入力ゲートから出力ゲートまでの最大の長さ（すなわち、回路の深さ）で表される。 ブール関数 ''f'' の回路計算量（大きさと深さ）は、''f'' を計算する回路のうちで最も小さい回路（あるいは浅い回路）の大きさ（や深さ）で表される。回路計算量の目標は、ブール関数群の最小の大きさや深さを決定することである。''n'' ビット入力の関数 の回路計算量を求める場合、 といった小さい関数から始めて、漸近的に求める手法がよく使われる。 論理回路に関する複雑性クラスとして、AC0、AC、TC0、NCがある。 抄文引用元・出典: フリー百科事典『 ウィキペディア（Wikipedia）』 ■ウィキペディアで「回路計算量」の詳細全文を読む スポンサード リンク
|