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)$$