プロンプトライブラリ
効率性の見積もり
関数とアルゴリズムの時間計算量を計算します。
このプロンプトを開発者コンソールにコピーして、自分で試してみてください!
内容 | |
---|---|
System | 提供された関数またはアルゴリズムを分析し、Big O記法を使用してその時間計算量を計算するのがあなたのタスクです。最終的な時間計算量にどのように到達したかを段階的に説明し、推論の過程を詳しく述べてください。時間計算量を決定する際には、ワーストケースのシナリオを考慮してください。関数またはアルゴリズムに複数のステップまたはネストされたループが含まれている場合は、各ステップの時間計算量を提供し、関数またはアルゴリズム全体の全体的な時間計算量を示してください。特に指定のない限り、使用される組み込み関数または操作の時間計算量はO(1)であると想定してください。 |
User | def example_function(n): for i in range(n): print(i) for j in range(n): for k in range(n): print(j, k) |
出力例
与えられた関数
example_function(n)
の時間計算量を分析するために、ステップに分解し、ワーストケースのシナリオを考えます。ステップ1: 最初のループの分析
for i in range(n): print(i)
このループは
n
回繰り返され、各反復で定数時間の操作 (print(i)
) を実行します。したがって、このステップの時間計算量はO(n)です。ステップ2: ネストされたループの分析
for j in range(n): for k in range(n): print(j, k)
外側のループは
n
回繰り返され、各反復で内側のループもn
回繰り返されます。内側のループの各反復で、定数時間の操作 (print(j, k)
) が実行されます。したがって、ネストされたループの時間計算量はO(n * n) = O(n^2)です。ステップ3: 時間計算量の組み合わせ
関数example_function(n)
は、最初のループとネストされたループの2つのステップで構成されています。全体の時間計算量は、各ステップの時間計算量の合計です。最初のループの時間計算量: O(n)
ネストされたループの時間計算量: O(n^2)全体の時間計算量を決定するには、最も高い増加の次数を持つ項である支配的な項を考慮します。この場合、O(n^2)がO(n)を支配します。
したがって、関数
example_function(n)
の全体的な時間計算量はO(n^2)です。ワーストケースのシナリオでは、
n
が大きい場合、ネストされたループが実行時間を支配し、関数は二次の時間計算量を持つことになります。