最大のパリンドローム部分文字列を見つけるアルゴリズムの複雑さ

Question

文字列が与えられています。 "acdfdcqqc"であり、最大のパリンドローム部分文字列を見つけるアルゴリズムを作成する必要があります。ここでは"cdfdc"です。 2N可能な出発のそれぞれについて

a - c - d - f - d - c - q - q - c 
1 0 1 0 1 0 5 0 1 0 1 0 1 4 1 0 1 

：これは、大きさ2nのアレイと中央IE用その時点で最大パリンドロームの長さを計算するたびに作成することにより、O（N^2）のアルゴリズムを考案することは簡単ですポイント私はその位置で始まる最大の回文の長さを見つける両方向に移動します。したがって、2n回の演算のそれぞれに対して、私は多くのO（n）回の演算を行います。したがって、O（n^2）時間の複雑さです。

私はそれがリニアタイムで好きなalgo：https://en.wikipedia.org/wiki/Longest_palindromic_substringを使って行うことができることを知っています。

しかし、扱っている文字列が自然な英語のテキストから抽出されていると仮定します。英語のテキストの中でランダムに位置を選ぶと、予想される対称性はかなり低いです。私は、予想される共産主義が各側に1文字未満であると言っています。 したがって、私のアルゴリズムは2n倍の期待される一定時間の演算をしており、アルゴリズムO（n）を平均していると言ってもいいですか？ O(n)時間は、それが可能なすべての入力のためにそうないことを意味期待

Answer 1

アルゴリズムの予想実行時間は、可能なすべての入力に対するアルゴリズムの平均実行時間です。教科書が指摘しているように、これを解決することは必ずしも容易ではなく、ランダムに選択された入力に対するアルゴリズムの実行時間などの代替手段を使用すると便利な場合もあります。しかし、原則は同じです。「予想される実行時間」の概念は確率的であり、アルゴリズムの多数のアプリケーションにのみ適用されます。対照的に、「最悪の場合の実行時間」は、（各長さの）任意の入力に対するアルゴリズムの最悪実行時間である。これは常に計算が容易であるとは限らないが、O（f（n））はf（n）が上位のものであるとしか言わないので、big-O表記の場合には問題ない、バウンド。

あなたが入力の制限された一連のアルゴリズムを適用する場合は、あなたが期待されるか、その制限されたセットの上に、時間を実行している最悪の場合のいずれかを指定することができます。入力が可能な入力の範囲に均一に分散していない場合は、予想される実行時間が計算されたときに考慮する必要があります。パリンドロームの長さの場合

入力は英語テキストのランダムに選択されたサブストリングである場合、最大のパリンドロームの予想される長さは（わずかに）ランダムに選択されたテキストの最大パリンドロームの予想される長さよりも長くなります小文字のセットとスペース文字から文字が引き出された文字列の世界全体。しかし、これらの入力セットの両方について、最も長い回文の期待される長さはO（1）です。

したがって、入力文字列の範囲の性質も指定する必要がありますが、あなたのアルゴリズムは「期待O（n）」と言ってもいいです。しかし、アルゴリズムへの入力を制御できない場合、最悪のケースの実行時間も関係します。なぜなら、あなたのナイーブなアルゴリズムのために最悪の場合の入力を作るのは簡単なので、それに対するDoS攻撃は明らかです。

Answer 2

号アルゴリズム設計で

は、アルゴリズムが実行されていると言うこと。つまり、入力が制限されたセットから無作為に一様に選択されるという事実にではなく、アルゴリズムのランダム性（内部コインフリップ）に期待する必要があります。

ただし、アルゴリズムが正しくないわけではありません。入力が英語のテキストに限定されているので、一般的な入力よりもアルゴリズムを速くする特定の特性を持つという事実を利用することはOKです。しかし、使用している用語（予想されるO(n)時間）は、すべての入力で実行時間がO(n)になると予想されるアルゴリズム用に予約されています。