3

私は同僚にアルゴリズム分析の基本を説明するためのプレゼンテーションを準備しようとしています-彼らの中にはこれまでこの主題について講義したことがない人もいますが、誰もが少なくとも数年は彼らの背後にあるプログラミングと優れた数学のバックグラウンドを持っています。私はこれを教えることができると思います。概念をうまく説明することはできますが、それらを実証できるように、要因をもたらすいくつかのコード構造またはパターンの具体的な例が必要です。

幾何学的要素(n、n ^ 2、n ^ 3など)は、同じ歩哨を使用した簡単な埋め込みループですが、あまり一般的ではないもののいくつかを説明して披露する方法に迷っています。

指数(2^nまたはc^n)、対数(n log(n)または単にlog(n))、および因子(n!)の要素をプレゼンテーションに組み込みたいと思います。これらをコードで取得するための短くて教えられる方法は何ですか?

4

4 に答える 4

3

問題を半分に分割するたびに一定量の作業を行う分割統治アルゴリズムはですO(log n)。たとえば、二分探索。

問題を半分に分割するたびに線形量の作業を行う分割統治アルゴリズムはですO(n * log n)。たとえば、マージソート。

指数関数と階乗は、セットのすべてのサブセット、またはセットのすべての順列をそれぞれ反復することによって、おそらく最もよく示されます。

于 2012-09-12T17:04:31.730 に答える
2

指数関数:ナイーブなフィボナッチの実装

n log(n)または単にlog(n):並べ替えバイナリ検索

階乗:ナイーブな巡回セールスマンソリューション。NP完全問題に対する多くの素朴な解決策。

于 2012-09-12T17:06:08.170 に答える
2

n!問題は非常に単純です。NP完全nがたくさんあります!巡回セールスマン問題などの時間の問題

于 2012-09-12T17:05:05.260 に答える
0

疑わしい場合は、ソートアルゴリズムの1つを選択してください-誰もが自分が何をすべきかを知っているので、複雑さに関する説明は簡単です:ウィキペディアには非常に優れた概要があります

于 2012-09-12T17:09:09.217 に答える