クイックソートを作成し、ピボット値に線形時間がかかるとします。最悪の場合の実行時間の再帰を求めます。
私の答え: T(n)= T(n-1) + T(1) + theta(n)
サブアレイが完全に不均衡な場合、最悪のケースが発生します。一方のサブ配列には 1 つの要素があり、もう一方のサブ配列には (n-1) 個の要素があります。theta(n) は、ピボットを見つけるのに実行時間 n がかかるためです。
私はこれを正しくやっていますか？
クイックソートを作成し、ピボット値に線形時間がかかるとします。最悪の場合の実行時間の再帰を求めます。
私の答え: T(n)= T(n-1) + T(1) + theta(n)
サブアレイが完全に不均衡な場合、最悪のケースが発生します。一方のサブ配列には 1 つの要素があり、もう一方のサブ配列には (n-1) 個の要素があります。theta(n) は、ピボットを見つけるのに実行時間 n がかかるためです。
私はこれを正しくやっていますか？