No.1ベストアンサー
- 回答日時:
計算量は n のみに依存し x には依存しません. なので, exponent(x, n) の計算量を T(n) とおきます.
T(0) = O(1), T(n) = T(n-1) + O(1)
と書けます. この漸化式を解けば T(n) = O(n).
「exponent が n回呼ばれるから O(n)」というのは省略しすぎです. exponent の中の (再帰呼び出し以外の) 計算量が O(n) だったら, そのようには言えませんよね.
「exponent の中で再帰呼び出し以外の計算量が O(1) で, exponent そのものは都合 n回呼び出されるから O(n)」とまで書いてあればいいかもしれない. 読む人によってよいとしたりだめとしたりするかもしれません.
お探しのQ&Aが見つからない時は、教えて!gooで質問しましょう!
似たような質問が見つかりました
- C言語・C++・C# C言語 3 2022/10/04 15:07
- 大学・短大 C言語線形リストの問題です 3 2022/12/22 00:45
- その他(プログラミング・Web制作) 十進BASICでの再帰についての質問です。 2 2022/11/18 09:17
- C言語・C++・C# c言語の問題です 3 2023/01/10 16:15
- C言語・C++・C# C言語階乗の総和を求める 2 2023/03/04 23:31
- C言語・C++・C# プログラミングのペーパーテスト 実行結果を表示せよ #include <stdio.h> int h 1 2022/07/09 15:27
- C言語・C++・C# C言語 3 2022/11/09 13:27
- C言語・C++・C# leetcode 155 minstack 1 2022/05/07 16:43
- C言語・C++・C# C言語プログラム変更 2 2022/12/21 15:03
- C言語・C++・C# 10人分の生徒の英語の点数{32,34,41,38,40,26,14,46,42,50} と数学の点 2 2022/05/26 21:31
このQ&Aを見た人はこんなQ&Aも見ています
関連するカテゴリからQ&Aを探す
おすすめ情報
このQ&Aを見た人がよく見るQ&A
デイリーランキングこのカテゴリの人気デイリーQ&Aランキング
-
Vb6.0で三角関数が使えない
-
変化させるセルが変化しない
-
やってみてもわからないので教...
-
C# 計算処理中に実行中ウィン...
-
MATLABの積分について
-
C言語で、漸化式を使ってパスカ...
-
スライムがつぶれていく様子を...
-
絶対ち
-
VBAの再計算が反映されない件に...
-
JavaScriptでSQLiteの値を使いたい
-
Excel VBAの残業時間の合計計算...
-
VBでReplace
-
Java 電卓の連続計算
-
あのコンピュータアーキテクチ...
-
60進数の四則計算
-
バッチファイルでウインドウを...
-
スパイダソリティアの問題
-
MathematicaのNDSolveで連立常...
-
65536は2の何乗なのでしょうか?
-
素数を自動的に作る
マンスリーランキングこのカテゴリの人気マンスリーQ&Aランキング
-
65536は2の何乗なのでしょうか?
-
VBAの再計算が反映されない件に...
-
排他的論理和 BCC(水平パリテ...
-
EXCELなどで「返す」という表現
-
C言語の課題で、1年の秒数を計...
-
バッチファイルでウインドウを...
-
骨折リスク評価のFRAXについて...
-
変化させるセルが変化しない
-
CとFORTRANの計算速度はどちら...
-
なぜオーバーフローになるので...
-
数値計算の高速化 (cos, sin, exp)
-
モジュラス103の計算とは何でし...
-
C# 計算処理中に実行中ウィン...
-
モジュロ
-
引き放し法による除算アルゴリ...
-
60進数の四則計算
-
C言語についてです。 再帰を使...
-
Perlで時間の計算
-
CRC8を教えてください
-
傾いた四角形内の範囲の条件式
おすすめ情報