私の高校論文の一部として、私は旅行セールスマン問題のヒューリスティックスについて説明しています。 読んでいた この ケーススタディ（8ページ）のようなものですが、私はこれらの文章の意味を理解できません。
説明したNNの実行時間はΘ（N ^ 2 ）。 [...] 特に、NN（I）/ OPT（I）≦（0.5）（log_ {2} N + 1）が保証されます。
その部分は私には非常に明確です。しかしその後：
実質的に しかしながら、より良い保証が可能であるが、 Θ（logN）として成長する。
の意味は何ですか 以下のためのインスタンスがあります？
同じことが貪欲なアルゴリズムで起こります：
...しかし最悪 グリーディ（Greedy）で知られている例は、（logN）/（3loglogN）として比率を増加させるだけである。
だから、その声明の意味は何ですか？ それは非ユークリッドのインスタンスと関係がありますか（それを解決するために距離行列の列を読むだけで済むので、そうは思わないでしょうか？）ソリューションツリーやそれに類するものを分割するアルゴリズムが必要な開始ノード？
編集： @templatetypedefのおかげで（あなたの答えは正しいものとして受け入れられます）、それはすべて意味があります。しかし、私は誰かが（または単なるリンク）の例を知っているかどうか尋ねたいと思います 特定のグラフ （私はどのアルゴリズムの問題でもありません）。話題があまりにも多すぎるとは思っていません。
回答：
回答№1は1これら2つのステートメントを並べて見てみましょう：
特に、NN（I）/ OPT（I）≦（0.5）（log_ {2} N + 1）が保証されます。
しかしながら、比率がΘ（logN）として増加する場合があるので、実質的により良い保証は可能ではない。
この最初のステートメントは、アルゴリズムNNは、最悪の場合は、正解のN（1/2）以内に答えを出します（これを見るにはOPT（I）で両面を掛けてください）。自然なフォローアップの質問は、実際の境界がそれよりもさらに厳しいかどうかです。例えば、その結果は、NN（I）/ OPT（I）≤log log N、またはNN（I）/ OPT（I）≤2の可能性を排除するものではない。
それは第二の声明がどこに来るかです。 このステートメントは、比率NN（I）/ OPT（I）がΘ（log n）であるTSPの既知のインスタンス（つまり、重み付けされた特定のグラフ）が存在することを示しますグラフのノード数の合計）。このようなインプットについては既に知っているので、NN（I）/ OPT（I）はログ・ログnまたは2のようなものから境界を定めることはできません。
しかし、その2番目の声明は孤立しているそれほど役に立たない。私たちは、アルゴリズムが原因でログファクタによって何かを引き起こす入力があることを知っていますが、さらに多くのものによってオフになるような入力がある可能性があります;例えば、指数関数的な要素最初のステートメントでは、ログファクタを超えることはないと知っているので、これが起こらないことがわかっています。
これらのステートメントを2つのステップで考える：最初のステートメントは、 上界 近似がどれほど悪いか - それは決して最適の1/2 l N + 1因子よりも悪くない。 下限 近似がどれくらい悪くなるかについて、アルゴリズムが最適解のΘ（log N）近似よりも良いことをすることができない特定の場合があります。
（ここで、Θ（log n）はランタイムとは何の関係もないことに注意してください。これは単に「何か対数型」と言っています）
今後は、上限と下限の両方に注目してください。 2人はまとめて、個別に行うよりもはるかに多くを伝えます。
論文と運が良かった！