- ベストアンサー
アルゴリズムの計算量とオーダ
多項式P(x) = (AnX＾n)+(An-1X＾n-1)+…A1X+A0と、この式を変形した P(x) = (…((AnX+An-1)X+An-2)X+…+A1)X+A0を、式どおりに計算すると各々の演算回数はどうなるでしょうか？ (Aの横のnや１などの数字は配列番号です) また、これらの結果をオーダ表記で表す場合どのように考えれば良いでしょうか？ よろしくおねがいします
- nullnull00
- お礼率60% (6/10)
- その他([技術者向] コンピューター)
- 回答数2
- ありがとう数1
- みんなの回答 （2）
- 専門家の回答
関連するQ&A
- 数列の問題で。。。
（X＋１）^nを X^2－２Ｘ－２で割った余りを AnX＋Bn (n＝1,2,3・・・）とする。 An＋１、Bn＋１をそれぞれAn Bnを用いて表せ。 という問題があり、 解答では、 （X＋１）^n＝（X^2－２Ｘ－２）Q（X）＋AnX＋Bn ・・・・(1)とおく。 (1)の両辺に（X＋１）をかけて、 （X＋１）^n＋１＝（X^2－２Ｘ－２）（X＋１）Q（X）＋AnX（X＋１）＋Bn（X＋１）(2) ＝（X^2－２Ｘ－２）（X＋１）Q（X）＋AnX（X^2－２Ｘ－２）＋（３An＋Bn）Ｘ＋（２An＋Bn)・・・・(3) これより An＋１＝３An＋Bn Ｂｎ＋１＝２An＋Bn ということだそうですが、(3)以下がまったくわかりません。 なぜ、(2)の式から(3)の式になったのでしょうか？ よってAn＋１＝３An＋Bn Ｂｎ＋１＝２An＋Bn になるのも、なぜなのかわかりません。。。。
- ベストアンサー
- 数学・算数
- 数列 漸化式
こんばんは、 数列の漸化式、特性方程式について質問します。 Ａn+1＝pＡn+q（n＝１，２，３、、）p,qは定数はα=pα+qを満たすαを用いて、Ａn+1-α=p（Ａn-α）と変形出来ますよね。 そこで質問なのですが、Ａn+1＝pＡn +qはＡn+1とＡnが連続しているからαと置いて、変形できるんですよね？ ある問題を解いていて、Ａ2n+1=1/2Ａ2n-1 +1/2（n＝１，２，３、、）という式も、 特性方程式を用いて、Ａ2n+1-1=1/2（Ａ2n-1－1）と変形していました。こちらの式は、Ａ2n+1とＡ2n-1は連続していませんよね？ 私の、特性方程式の使い方間違っているんでしょうか？ よくわからないので、教えていただきたいです。お願いします！
- ベストアンサー
- 数学・算数
- 原始多項式について
一意分解環Aとその多項式環A[x]∋f(x)について、次の(1), (2)は同値であることを証明したいのですが、 (1)f(x)は原始多項式である (2)任意の素元p∈Aに対して、f(x)をpを法として考えた多項式f'(x)∈(A/(p))[x]は零でない (2)のf(x)をpを法として考えた多項式とは a0, b0, …, an, bn∈Aを用いて f'(x)=(a0/pb0)x^n+…+(an-1/pbn-1)x+(an/pbn) と表せる事(だと思う、、)で、 原始多項式とは f(x)=a0x^n+…+an-1x+anについて、a0, …,anの最大公約元が可逆元であることなので、 (2)⇒(1)はf'(x)=(a0/pb0)x^n+…+(an-1/pbn-1)x+(an/pbn)が零でなければ、a0, …,anの最大公約元が可逆元となるように示して行けば良いと思うのですが さっぱり分かりません。 (1)⇔(2)の証明をご教授頂けると助かります。 よろしくお願いいたします。
- ベストアンサー
- 数学・算数
- このアルゴリズムを何回繰り返せばよいのか。
次のようなアルゴリズムＡがある。 Ｐ(ｘ)＝１であるような入力ｘに対しては必ず正しい答え１を出すが、 Ｐ(ｘ)＝０であるような入力ｘに対しては確率0.001で正しい答えを出し、 確率0.999で間違った答えを出す。 この時、どんな入力に対しても確率0.99以上で正しい答えを出すアルゴリズムを構成せよ。 という問題なのです。 答えは 0.01 ＞ (0.999)**ｎ （ (0.999)**ｎは0.999のｎ乗の意味 ） が成り立つ最小のｎ回アルゴリズムを繰り返せばよいと考えたのですが、 この式を解くとｎが2000以上になると思います。 難しくてきちんとしたｎの値は出てきませんでした。 何かこの式を簡単に解く式変形の仕方ってありますか？？ それともこの問題をこの式で解くのが間違っているのでしょうか？？？ よろしくお願いします！！！
- ベストアンサー
- 数学・算数
- 解析の証明がわかりません。
解析の問題です。 問、多項式ｆ（ｘ）を（ｘ－α）の多項式ｆ（ｘ）＝ａ０＋a1x＋a2x^2＋…＋anx^nについて次の問いに答えよ。 （１）ｆ（ｘ）を（x-α）の多項式ｆ（ｘ）＝ｂ０＋ｂ１（ｘ－α）＋ｂ２（ｘ－α）＾２＋…＋ｂn（ｘ－α）＾nとあらわすとき、ｂｋ＝ｆ＾（ｋ）（α）/ｋ！ （ｋ＝０，１，２，…，ｎ）となることを示せ。 （２）ｘ＝αが方程式ｆ（ｘ）＝０のｋ重根であるための必要十分条件は、 ｆ＾（０）（α）＝ｆ＾（１）（α）＝ｆ＾（２）（α）＝…＝ｆ＾（k‐1）（α）＝０ ， ｆ（ｋ）（α）≠０ であることを示せ。 の示し方がわかりません。 わかる方は教えてください。お願いします。
- 締切済み
- 数学・算数
- 高校数列
数列｛An｝の初項から第n項までの和をSnとする。A2=３． ｎ・Ｓn=(n－1)(2An＋2－n) (n＝1、2、3・・・・・)を満たし手いるとき (1) 数列｛An｝はｎ・A(n＋1)－2(n＋1)・An＝n＋2 ・・(1) (n＝1、2、3・・・・・)を満たすことを証明せよ (2) Anをnの式で表せ ちなみにA(n＋1)は数列｛An｝の第n＋1項を意味します この問題で(1)は証明できたのですが(2)での解答で ｎ・A(n＋1)－2(n＋1)・An＝n＋2 ・・(1)から ｎ(A(n＋1)＋1)＝2(n＋1)(An＋1)という変形がみられるのですがどうしてそうなるのかわかりません。確かに両辺に＋nをすると変形できたり 。あるいは特性方程式よりα＝1と求まり変形できるのですが、ここでは変数nがあるので特性方程式が利用できるのかもわかりません。 どなたかわかる人がいましたらお願いします。
- ベストアンサー
- 数学・算数
- 以下の問題が与えられたのですが、
以下の問題が与えられたのですが、 (4)という定義なしに答える方法はあるのでしょうか？ 本問では(4)という定義はありません。 どなたか教えていただけると助かります。 質量m、角振動数ωの1次元調和振動子の ハミルトニアンは(1)式で与えられる。 ここでp（＾は省略します）は運動量演算子、 xは位置演算子であり、交換関係[x,p]=xp-px=ih/2πを満たす。 また、(2)、(3)で定義される2つの演算子を考える。 演算子N=a†aの固有値をnとし、 その規格化された固有状態を|n>とする。 すなわちN|n>=n|n>,<n|n>=1である。 次の2つの関係式が成り立つことを示し、 係数A,Bを求めよ。 a†|n>=A|n+1>, a|n>=B|n-1> ただしA,Bは正の実数とする。
- ベストアンサー
- 物理学
- アルゴリズムの計算量O(ｎ)の証明
O()ビッグオーダについての証明問題なのですが どうすればよいのかわかりません。どなたか教えていただけませんか？ O(n*log n + n) = O(n*log n)を証明せよ f(n) ε O(n) f(n) > 0で、ある定数Cがあり ここでlim n→∞ f(n)/n ≦ C おそらく上を使うと思うのですが式変形を行っても 左辺-右辺で0にできません。ひょっとしたら はさみうち等を使うのでしょうか？ よろしくお願いいたします。
- 締切済み
- 科学
- 線形代数の問題がわかりません。教えてください。
次のｎ元同時連立一次方程式を解け。ただしa1+a2+‥+an=1である。 （a1-1）x1+ a1x2+‥a1xn =0 a2x1+(a2-1)x2+‥a2xn =0 ‥‥‥‥‥ anx1+ anx2+‥(an-1)xn=0 という問題です。
- 締切済み
- 数学・算数
お礼
ご回答頂きありがとうございます 変形前と変形後の多項式では結果がここまで変わるものなんですね。