アルゴリズムの複雑さとは何ですか？

アルゴリズムの複雑さ（計算の複雑さ、またはコルモゴロフの複雑さ）は、計算の複雑さ理論およびアルゴリズム情報理論の両方の基本的なアイデアであり、正式な誘導において重要な役割を果たします。

バイナリ文字列のアルゴリズムの複雑さは、文字列を生成できる最短かつ最も効率的なプログラムとして定義されます。 特定の文字列を生成できるプログラムは無限にありますが、1つのプログラムまたはプログラムグループが常に最短になります。特定の文字列を出力する最短アルゴリズムを見つけるアルゴリズムの方法はありません。これは、計算複雑度理論の最初の結果の1つです。それでも、私たちは教育を受けた推測をすることができます。 この結果（文字列の計算の複雑さ）は、計算可能性に関連する証明にとって非常に重要であることが判明しています。

物理的なオブジェクトまたはプロパティは、一連のビット、オブジェクト、プロパティによってほぼ壊滅的に説明できるため、アルゴリズムの複雑さも援助します。 実際、オブジェクトを出力として生成するプログラムに現実世界のオブジェクトの複雑さを減らすことは、科学の企業を見る1つの方法です。 私たちの周りの複雑なオブジェクトは、3つの主要な生成プロセスから来る傾向があります。 emergence 、 evolution 、および Intelligence 。

計算の複雑さは、理論的なコンピューターサイエンスで頻繁に使用される概念であり、数学的および論理的な幅広い問題に対するソリューションを計算することの相対的な難しさを決定します。 400を超える複雑なクラスが存在し、追加のクラスが継続的に発見されています。 有名な p = np 質問は、これらの複雑さの2つのクラスの性質に関するものです。 複雑なクラスには、何よりもはるかに難しい問題が含まれます計算まで数学で直面するかもしれません。 計算の複雑さ理論には、解決するのに近接している時間を必要とする多くの想像上の問題があります。

アルゴリズムの複雑さと関連概念は、1960年代に数十人の研究者によって開発されました。 Andrey Kolmogorov、Ray Solomonoff、Gregory Chaitinは、60年代後半にアルゴリズム情報理論で重要な貢献をしました。 アルゴリズムの複雑さに密接に関連する最小メッセージ長の原理は、統計的および誘導的な推論と機械学習の基礎の多くを提供します。