A 回答 (2件)
- 最新から表示
- 回答順に表示
No.2
- 回答日時:
f(1)=f(2)=1 は既知として、単純にf(n)をそこまで式を展開してゆくと
項数も計算結果もフィボナッチ数列のn番目の値になって
O(n^2)ではない。
また、展開せずに f(3)から順に計算するだけなら
計算量はO(n) だろうし・・・・
まずO(n^2)が何に対する話なのか説明してください。
No.1
- 回答日時:
何が o(n^2) だって話をしているんだろう?
漸化式 f(n) = f(n-1) + f(n-2) で与えられる f(n) の値なら、o(n^2) ではない。
f(n) を求める計算量ならば、 f(1), f(2) の値から始めて
漸化式を n-2 回適用すれば求まるから、計算量は O(n) であって
o(n^2) のうちでもある。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
おすすめ情報
- ・漫画をレンタルでお得に読める!
- ・ゆるやかでぃべーと タイムマシンを破壊すべきか。
- ・「I love you」 をかっこよく翻訳してみてください
- ・歩いた自慢大会
- ・許せない心理テスト
- ・字面がカッコいい英単語
- ・昔のあなたへのアドバイス
- ・かっこよく答えてください!!
- ・あなたが好きな本屋さんを教えてください
- ・スタッフと宿泊客が全員斜め上を行くホテルのレビュー
- ・【大喜利】【投稿~8/27】 こんなガソリンスタンド二度と来るか!なぜそう思った?
- ・これ何て呼びますか Part2
- ・人生で一番思い出に残ってる靴
- ・【お題】動物のキャッチフレーズ
- ・【お題】甲子園での思い出の残し方
- ・ゆるやかでぃべーと すべての高校生はアルバイトをするべきだ。
- ・「それ、メッセージ花火でわざわざ伝えること?」
- ・自分用のお土産
- ・人生で一番お金がなかったとき
- ・一番好きなみそ汁の具材は?
- ・泣きながら食べたご飯の思い出
- ・ちょっと先の未来クイズ第1問
- ・ゴリラ向け動画サイト「ウホウホ動画」にありがちなこと
- ・初めて自分の家と他人の家が違う、と意識した時
- ・単二電池
- ・チョコミントアイス
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
この表現は正しいですか?
-
故 訳 由 この3つの使い分けを...
-
excel マクロ 「select case」...
-
日本男性の草食化の理由について
-
人の名前でなぜ薊とつけたらダ...
-
ダイエット成功者に質問です。 ...
-
わたしは高校受験で総合学科を...
-
今もしiPhoneを買うならばiPhon...
-
志願理由書の将来の夢について...
-
理由を聞くと、なんとなくと答...
-
小論文でテーマが家族
-
急いでいます!!!! 貴塾?
-
通信制高校の高校3年です 就職...
-
実力テスト150点は偏差値どのく...
-
高1(4月から高2)生です。 1月...
-
来年受験があります、偏差値39...
-
高校の文化祭 二日間?三日間?
-
英検3級できて偏差値どのくらい...
-
高校生(高卒)の就職は一発で...
-
学校サボって一人で外出した事...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
この表現は正しいですか?
-
理由を聞くと、なんとなくと答...
-
故 訳 由 この3つの使い分けを...
-
2023年、黒潮が北上している理...
-
「理由と道理」「理由と筋道」...
-
日本男性の草食化の理由について
-
人の名前でなぜ薊とつけたらダ...
-
面接で、 『趣味はなんですか?...
-
“焼肉のたれ” に白ゴマが入って...
-
excel マクロ 「select case」...
-
わざと誘わない人ってなんでで...
-
志望理由に将来の夢が実家を継...
-
Yahoo!知恵袋と教えてgoo。どっ...
-
「得られる」と「見ながら」の...
-
一番かっこいい物理学者は誰で...
-
偽善者に見える理由を 教えて下...
-
株価指数でFX
-
面接練習で将来の夢を聞かれて...
-
賃借権を目的として抵当権を設...
-
高校受験の志願理由書に汚れが…...
おすすめ情報