基本ケースの複雑さが一定でない再帰

Question

基本ケースの定数が一定以上の再帰アルゴリズムはありますか？ CLRSは、一般に再発は、ベースケースについて

T（N）= O（1）

を示すことを言います。非一般的なケースはどうですか？床と天井のケースはいつ無視できますか？

Answer 1

これは、関数定義に完全に依存します。あなたは好きなように再帰関数を作ることができます。例えば、このような配列ソート機能何かを想像：

1. If value range < 10, bubble-sort the array. 
2. Else find the midpoint of the range, split the array into two pieces (values above and below the midpoint) and recur on each piece. 
    Append the two pieces. 

再帰ステップは、単にO（ログベース2（list_range/10））です。 ベースケースはO（array_size^2）です。

ところで、それはシカではなく、筆記体「O」（「順序」==「順序」）です。

これは典型的な例ではありませんが、アルゴリズムの分割と征服の部分は、問題を扱いにくいものに減らすことはできません。パッケージされたサブルーチン。