アルゴリズムの複雑さに関する良いテキスト

Question

アルゴリズムの複雑さで優れた入門テキストをどこで探すべきですか？これまでのところ、私はアルゴリズムクラスといくつかの言語クラスを持っていましたが、理論的なバックボーンは何もありませんでした。私は完全な複雑さを得ますが、時々、O（1）とO（n）を区別するのが難しい場合があります。さらに、シータ表記全体とそのすべて、p = npの基本的な説明と単純なアルゴリズム、扱いやすさがあります。私はそれをすべてカバーするテキストが欲しいですが、それは重い数学的背景、または読み通すことができるものを必要としません。

LE：私はまだ大学ではなく高校にいます。重い数学的背景とは、おそらく計算や線形代数よりもそれほど高くないことを意味します（理解できないということではありません。たとえば、テイラーシリーズを学ぶという事実です計算を行わなければ、Iは少しストレッチです。それが私が数学的に重くないという意味です。通常の努力を伴う数学が理解できるものです）。そして、私が間違っている場合は恩赦をしますが、理論的に言えば、彼らがアルゴリズムの設計方法と実際のアルゴリズムを教えるクラスは「アルゴリズム」クラスと呼ばれるべきですよね？私の現在の理解、無限のシリーズ、制限と統合（私が知っている制限と積分）という点では（私が見たがそれらの概念を使用しているように見えました）が、高速フーリエ変換で私を失いました。

Answer 1

の本は私の非常に個人的な意見です ジョン・クラインバーグとエヴァ・タルドス 効率的なアルゴリズムの設計と分析を研究するのに最適な本です。それほど包括的ではないかもしれません Cormen et al。 しかし、それは素晴らしい教科書です。この本があなたの興味に最も合っていると思うのはなぜだと指摘させてください

• 証拠には重い数学の機械は必要ありません
• この本はしばしば何かが機能している（またはそうでない）大きな直感を与えます。これは私の意見では初心者や自己学習者にとって非常に重要です
• NP不完全性に対する非常に直感的なアプローチ
• それは、実際にNP完全な問題に対処する方法を持っている素晴らしい章を持っています
• デザインパターンに焦点を当てています。

また、利用可能なWWWには無料の資料がたくさんあることに注意する必要があります。素晴らしい 講義ノート ジェフ・エリクソンが提供しています。また、MITクラス全体を見ることもできます 「アルゴリズムの紹介」 チャールズ・レジャーソンとエリック・D・デメインによって教えられました。クール！

Answer 2

あなたは確かに有名な本に賭けることができます Cormen et al。 「アルゴリズムの紹介」。まず第一に、音の数学的基盤がない場合、本を理解することは非常に困難です。しかし、簡単に理解するためには、それらの数学的証明をスキップすることができます（推奨されません）。また、あなたは行くことができます アルゴリズム設計マニュアル.

Answer 3

M. Sipser'sを見る必要があります」計算理論の紹介「。私は高校にいたときにこの本を読んだ（そして理解した）ので、それはあなたに適していると思います。

それは非常にフォーマルですが、すべてが平易な英語でも説明されています。また、最初は証明技術の少し紹介があります。

---

注：深刻なレベルでCSを実行したい場合（例：研究）、 個体 数学の背景。近道はありません。すなわちグラハム、クヌース、パタシュニクを見てください 具体的な数学.