cycle of data science

math problems $$ N! ∈ \Omega (N^{N}) ? $$ √ $$ log(N!) ∈ \Omega (NlogN) ? $$ √ $$ NlogN∈ \Omega (log(N!)) ? $$ √ 所以可以推出： $$ NlogN ∈ \Theta (logN!) $$ $$ log(N!) ∈ \Theta (NlogN) $$ TUCS用时 上下界？ the ultimate comparison sort run time $$ \Omega(NlogN) $$ $$ O(NlogN) $$ 下面开始证明： 考虑下界，对n个物体进行排序，有N！种可能，用两两比大小，考虑决策树的高度$$ H = \log_2 N! $$ 因此下界为 $$ \Omega (log(N!)) $$ 或者 $$ \Omega (NlogN) $$ 上界通过TUCS的性质可以通过具体示例反证得到，比如用merge sort

More quick sort, Stability, Shuffling quick sort VS merge sort QuicksortL3S = left + 3-scan + shuffle Quicksort_LTHS: Tony Hoare partition scheme: L ptr 仅仅指向小的 G ptr 仅仅指向大的 ptr walk towards to each other, stopping on a hated item 两个都停下来的话， 交换一下， 然后移动其中一个 when ptrs cross, done. 和G交换pivot Not random smarter pivot selection: median Quicksort_PickTH 考虑了如何计算数组地址的复杂度， 以及如何选择pivot的复杂度。 worst case: $$ \Theta(NlogN) $$ 但实际上并没有那么好，因为计算中位数的复杂度是$$\Theta(N)$$。耗费了更多时间。 quick select–using partitioning worst case: a sorted array $$ \Theta(N^2) $$