班上学生多，很难记住名字啊 (转载)# Joke - 肚皮舞运动
c*r
1 楼
希望对Recursion Big-O complexity 分析有些疑惑的童鞋有些帮助
Recurrence Algorithm Big-O Solution
T(n) = T(n/2) + O(1) Binary Search O(log n)
T(n) = T(n-1) + O(1) Sequential Search O(n)
T(n) = 2 T(n/2) + O(1) tree traversal O(n)
T(n) = T(n-1) + O(n) Selection Sort (other n2 sorts) O(n^2)
T(n) = 2 T(n/2) + O(n) Mergesort (average case Quicksort) O(nlog n)
Recurrence Algorithm Big-O Solution
T(n) = T(n/2) + O(1) Binary Search O(log n)
T(n) = T(n-1) + O(1) Sequential Search O(n)
T(n) = 2 T(n/2) + O(1) tree traversal O(n)
T(n) = T(n-1) + O(n) Selection Sort (other n2 sorts) O(n^2)
T(n) = 2 T(n/2) + O(n) Mergesort (average case Quicksort) O(nlog n)
