1

時間複雑度とは何ですか? なんで？

(define (mult a b)
      (define (internal a accum)
        (if (= a 1) accum
            (internal (- a 1) (+ accum b))))
      (internal a b))

(define (to-the-power-of m n)
  (define (internal x accum)
    (if (= x 0) accum
        (internal (- x 1) (mult accum m))))
  (internal n 1))
4

2 に答える 2

3

マルチパートの時間計算量は次のように求めることができます:

(mult ab) を計算するには、(internal a accum) が a = 1 になるまで呼び出されるため、a を反復するある種の末尾再帰 (ループ) があります。

したがって、(mult ab) の時間計算量はO(a) (= 線形時間計算量)であることがわかります。

(to-the-power-of mn) には (内部 x accum) 定義もあり、これも (x = 0 まで) ループします。

繰り返しますが、O(x) (= 線形時間の複雑さ)があります。

しかし
: 内部の関数呼び出しに必要な時間を考慮していませんでした... (mult 1 m) --> O(1)
2 回目の繰り返し これは次のようになります: (mult mm) --> O(m)
3 回目の繰り返し: (mult m² m) --> O(m*m) そしてこれが n = 0 (または内部では x = 0 になる) まで成長することは明らかです。

したがって、時間の計算量は m と n に依存すると言えます: O(m^n)

[編集:] 私が以前に尋ねた関連する質問もご覧ください: Big O, how do you calculate/approximate it? これにより、近似をより一般的に処理する方法の手がかりが得られる場合があります

于 2008-10-30T09:25:37.217 に答える
0

加算と乗算の両方が 1 つの演算としてカウントされると仮定すると、この関数は O(m^n) 演算を実行します。

まず、mult 関数について考えます。これ (mult ab) は、正確に a-1 の加算を実行します。漸近成長は同じなので、数学的に簡単にするために、これを a で近似します。

to-the-power-of 関数の場合、これは mult 関数への n 回の呼び出しを実行します。これらの呼び出しは、to (mult 1 m)、yield m、次に to (mult mm)、yield m^2、次に to (mult m^2 m)、yield m^3 というように m^n まで続きます。したがって、ここで実行される操作の総数は、合計 m^0 + m^1 + ... + m^n です。これは、m^n として成長する (m^n - 1) / (m-1) です。

于 2008-10-30T09:23:53.273 に答える