多項式時間複雑度の負の係数

Question

多項式時間の複雑さがあるアルゴリズムを仮定すると、T（n）のいずれの項も負の係数を持つことは可能ですか？直感的には、前の手順で取った既存の時間を短縮するアルゴリズムはないので、答えは明白な「いいえ」のように見えますが、私は確信しています。

Answer 1

多項式の複雑さについて言及するとき、最も高い次数の係数だけがカウントされます。

しかし、あなたはT（n）= n * n - n = n *（n-1）を持つことができると思います。 n-1は、最初または最後の繰り返しでやっていないことを表します。

とにかく、複雑さはまだn * nです。

Answer 2

アルゴリズムの時間の複雑さは負の係数を持つ可能性がありますが、アルゴリズム全体ではいくらかの正の時間の複雑さがあります。ウィキペディアのexampleとして、f(x)=6x^4-2x^3+5の機能を利用してください。 X0およびMのいくつかの適切な選択のために、すべてのx> X0ため

を次のように彼らはO(x^4)の複雑さのために解決します。これを証明するために、聞かせX0 = 1、M = 13次に、ためすべてのx> X0：

ので、あっても、ある

元の方程式の負の係数では、最も高い次数の項に基づいていくつかの正の全体的な時間複雑さが依然として存在する。

---

下限はどうですか？定義では、我々は次のようdefinitionを使用して、任意の関数の下限を見つけることができます：nは無限大に進むにつれ、その後、いくつかの定数kといくつかのn0のために、我々は次のようにすべてのn>n0のために保持していることがあります。

上記の関数f（x）もオメガ（x^4）であるとします。^2X -

K < =（6X^4：2X^3 + 5> = KX^4

kについて解く -

6X^4：これがあることを意味します3 + 5）/（X^4）

K < = 6 - 2X^-1 + 5X^-4

（5/x^4）のように、（2/x）という用語は0に近づくため、大きなx0 = 30に対してはk=2を選択できます。 - 2X^3 + 5> = 2X^x>は30

の4x^4 4 - > = 0×2^3 + 5

6X^4：これが成り立つことを示すために、我々はことを示しています

したがってf(x)はオメガ（x^4）であり、f(x)がシータ（x^4）であるようなタイトな境界が見つかったと結論づけることもできます。

係数が負であっても、これはなぜ機能しますか？ Big OとBig Omega表記の両方で、のある点の後にの関数が別の関数を支配するような境界を探しています。つまり、as these graphs illustrateです：

http://cs.anu.edu.au/~Alistair.Rendell/Teaching/apac_comp3600/module1/images/Introduction_BigOGraph.png - ビッグO

http://cs.anu.edu.au/~Alistair.Rendell/Teaching/apac_comp3600/module1/images/Introduction_BigOmegaGraph.png - 私たちの元f（x）が考えるビッグオメガ

、6x^4は2x^4（当社キロ（xよりも速く成長します） 関数）。 のいくつかのポイントの後に、6x^4という用語は、常に2x^4より大きいように、2x^4の成長を上回ります。グラフィカルに、2つの関数は次のようになります。負の係数にもかかわらず

http://www3.wolframalpha.com/Calculate/MSP/MSP8991a0763a90cg9c64500002i49d6b33c5684hg?MSPStoreType=image/gif&s=47&w=319&h=132&cdf=RangeControl

、はっきりkg(x)はf(x)の下限です。

---

さて、これは任意の負の係数を持つ多項式関数については常に真である - 任意の係数を持つ関数f(x)が最高度の多項式に拘束されることになるということ？いいえ。最高度の項に負の係数がある場合、境界は全く同じではありません。 f(x) = -2x^2とする。 （cは、定義により、正の定数であるように）任意c>0によって満足することができる

-2x^2 < = CX^2 -2 < = C

：我々はf(x) = O(x^2)ことを示すことができます。しかし、私たちは下界のための同じをしようとした場合：

-2x^2> = CX^2 -2 < = C

その後、我々は右のcを見つけることができないため、再びcは負でない必要があります。