注：本博文来自Yang Enzo博客园，感谢作者整理。

 

:Introduction to Algorithms P95

T(n) = 3 * T(2*n/3) + O(1)

According to master method,this situation suits the first case.

1 ///Test Code/ 2 #include "stdafx.h" 3 #include "stdlib.h" 4 #include 
     
       5 #include "basic_algorithm.h" 6 #include 
      
        7 using namespace std; 8  9 10 int _tmain(int argc, _TCHAR* argv[])11 {12     13     srand((unsigned)time(NULL));14     int *arr = new int[20];15     for(int i = 0; i < 20; ++i)16     {17         arr[i] = rand() % 30;18     }19     enzo::stooge_sort(arr,20);20     for(int i = 0; i < 20; ++i)21     {22         cout << arr[i] << " ";23     }24     cout << endl;25     system("pause");26     return 0;27 }28 29 ///Source Code///30     template
       
        31     void stooge_sort(_T *arr, int n)32     {33         stooge_sort(arr, 0, n-1);34     }35 36     template
        
         37     void stooge_sort(_T *arr, int from, int to)38     {39         if(arr[to] < arr[from])40         {41             ez_swap(arr[to], arr[from]);42         }43         if(from + 1 < to)44         {45             int k = (to - from + 1) / 3;46             stooge_sort(arr, from, to - k);47             stooge_sort(arr, from + k, to);48             stooge_sort(arr, from, to - k);49         }50     }
        
       
      
     

 

T(n) = O(n^(log(2/3, 3) > O(n^2)