再帰を含むアルゴリズムの複雑さを見つける必要があります。
T(n) = T(n-1) + ... + T(1) + 1
T(n)サイズの問題を解くのにかかる時間nです。
マスター メソッドはここでは適用されず、置換メソッドを使用する推測もできません (とにかく置換メソッドを使用したくありません)。再帰ツリー法が残っています。
各ノードの子の数は一定ではないため、各ノードがどれだけ貢献しているかを追跡するのは難しいと感じています。根本的なパターンは何ですか？
k各ノード ( ) がその子に対して 1 から までの番号が付けられたすべてのノードを持つツリー内のノードの数を見つける必要があることを理解していますk-1。
T(n)その式から正確な時間を見つけることも可能ですか?