関数 A が O(n^2) 時間で実行される n^c 個の関数 B を呼び出す場合、関数 A の時間計算量はどれくらいですか? 多項式（n ^ c）だけでなく、cが大きくなっただけですか？
1 に答える
5
関数Aが別の関数Bを呼び出す場合、複雑さの合計はAとBの複雑さの積になります。したがって、この場合、合計の複雑さは O( n c · n 2 ) = O( n c + 2 ) です。
製品の一般規則:
ƒ 1 ∈ O( g 1 ) および ƒ 2 ∈ O( g 2 ) ⟹ ƒ 1 ·ƒ 2 ∈ O( g 1 · g 1 )
ƒ·O( g ) ∈ O(ƒ· g )
于 2010-10-13T06:32:14.817 に答える