非決定性計算量（読み）ひけっていせいけいさんりょう

世界大百科事典（旧版）内の非決定性計算量の言及

【アルゴリズム】より

…出発点から次々と〈適切な都市〉を選んで行けるなら，都市数nに比例する時間でハミルトン閉路(もしあれば)を発見できるので，これらの基準によれば計算量はnの1次式になる。これを〈非決定性アルゴリズムの計算量〉，あるいは〈非決定性計算量〉という。なおこれらと対比するときは従来のアルゴリズムを〈決定性アルゴリズム〉，計算量を〈決定性計算量〉という。…

※「非決定性計算量」について言及している用語解説の一部を掲載しています。

出典｜株式会社平凡社「世界大百科事典（旧版）」