A 回答 (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) のうちでもある。
No.2
- 回答日時:
f(1)=f(2)=1 は既知として、単純にf(n)をそこまで式を展開してゆくと
項数も計算結果もフィボナッチ数列のn番目の値になって
O(n^2)ではない。
また、展開せずに f(3)から順に計算するだけなら
計算量はO(n) だろうし・・・・
まずO(n^2)が何に対する話なのか説明してください。
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- C言語・C++・C# C言語 3 2022/10/04 15:07
- C言語・C++・C# numpyスライス機能を使った数値計算 2 2023/05/08 16:01
- 建設業・製造業 掛け率の計算について 3 2021/12/17 07:57
- 数学 以下の計算のコツを教えて下さい。 ①483×434×2 ②64×17÷10 ③31×6×28 ④28 7 2022/02/02 15:51
- 確定申告 確定申告のやり方がまったくわかりません…いろんなサイト見てもいまいちわからないです。教えてください。 2 2021/11/22 18:25
- 統計学 統計学の質問です。 どなたか分かる方教えて頂けたら幸いです。 共通]下記の仮説の真偽を判断するため, 2 2021/12/21 18:13
- 物理学 高分子の広がりについての問(自由連結鎖)です。 1は、√10000×2.51^2 で合っているでしょ 1 2021/12/23 10:59
- Excel(エクセル) EXCELの動作を早くする方法 4 2021/12/16 17:34
- C言語・C++・C# このプログラミングの問題を教えてほしいです。 キーボードからデータ数nとn個のデータを入力し、平均値 3 2022/12/19 22:51
- 工学 糸の長さがa[m]で、AB間の距離がa×cos45°×2と解説にあったんですが、何故cosを使って計 3 2021/11/28 15:55
このQ&Aを見た人はこんなQ&Aも見ています
-
プロが教えるわが家の防犯対策術!
ホームセキュリティのプロが、家庭の防犯対策を真剣に考える 2組のご夫婦へ実際の防犯対策術をご紹介!どうすれば家と家族を守れるのかを教えます!
-
直感力を高めるほうほうっていう、
数学
-
大きな数の掛け算
数学
-
−2.5を四捨五入すると−2ですか?−3ですか?
数学
-
-
4
えfor文とか使っちゃう時点で時間計算量ってO(1)にはなりませんか?たとえば長さmの配列についてf
計算機科学
-
5
'='と':='の記述の違い
計算機科学
-
6
なんで2πをかけるのかがわからないです。
計算機科学
-
7
蓮舫の「2位じゃダメなんですか?」
計算機科学
-
8
ATMの暗証番号は 0から9の数字から 4回数字を取り出し4桁の数字を作るので 10の4乗で1000
数学
-
9
階差数列の問題で、n=1にときに成り立たない問題を見たことありますか?
数学
-
10
数学の質問です(あえてMODは使わないで証明)
数学
-
11
確率の問題を解説していただきたいです。 a,b,c,d 4つの部屋があります。 外に出ると移動が終了
数学
-
12
数値計算の時間の刻み幅について
計算機科学
-
13
「自然数は無限」としてよいのか?
数学
-
14
この議論めちゃ怪しくないですか?? F = ma 空間で微分(簡単のため一次元) ∫F=∫m dv/
数学
-
15
ハノイの塔のさいきアルゴリズムがめちゃ考えても全然意味わからないし再帰関数が、ほんとに苦手なんですけ
システム科学
-
16
自明の証明
数学
-
17
パソコン用語ひとつもわかりません
計算機科学
-
18
x^2−6x+5=0はx=1であるための何条件か?という問題で、答えは必要条件なのですが、解説をお願
数学
-
19
nに1足した数が、
数学
-
20
問題解決力を鍛える!アルゴリズムとデータ構造 ていうの届いたんですけど、c言語がわかりません。 それ
数学
おすすめ情報
このQ&Aを見た人がよく見るQ&A
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
この表現は正しいですか?
-
アップルウォッチって出たとき...
-
小論文でテーマが家族
-
“焼肉のたれ” に白ゴマが入って...
-
故 訳 由 この3つの使い分けを...
-
再帰的なプログラムの時間計算量
-
面接で、 『趣味はなんですか?...
-
人の名前でなぜ薊とつけたらダ...
-
志望理由に将来の夢が実家を継...
-
高1物理基礎の相対速度の問題が...
-
東北大学、神戸大学、筑波大学...
-
学校サボって一人で外出した事...
-
急いでいます!!!! 貴塾?
-
なぜ学校では偏差値が上がるほ...
-
昔と今は偏差値の出し方が違う...
-
工学院大学って世の中的にどの...
-
専門学校辞める=甘えですか? ...
-
英検3級できて偏差値どのくらい...
-
ドラマやマンガでの、「架空の...
-
中学生の頃すごく頭が良くて、...
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
この表現は正しいですか?
-
故 訳 由 この3つの使い分けを...
-
反出生主義の人がモテないって...
-
平成22年度電検王さんの問題に...
-
初恋でなく2番目の恋で結婚する...
-
理由を聞くと、なんとなくと答...
-
面接で、 『趣味はなんですか?...
-
excel マクロ 「select case」...
-
“焼肉のたれ” に白ゴマが入って...
-
Yahoo!知恵袋と教えてgoo。どっ...
-
人の名前でなぜ薊とつけたらダ...
-
賃借権を目的として抵当権を設...
-
再帰的なプログラムの時間計算量
-
Xperia1マークIIからGALAXY S20...
-
一番かっこいい物理学者は誰で...
-
振った理由きいたらだめなん? ...
-
「理由と道理」「理由と筋道」...
-
少子高齢化の原因は
-
高校受験の志願理由書に汚れが…...
-
志望理由に将来の夢が実家を継...
おすすめ情報