構(gòu)造一顆N元素的最小堆最壞的時(shí)間復(fù)雜度用O表示是多少？最壞的情況是，每次將第i個(gè)元素放入堆中時(shí)，該元素都必須上移logi次，因此構(gòu)建最小堆的最壞時(shí)間復(fù)雜度是Log1 log2。。。Logn=Log1*

構(gòu)造一顆N元素的最小堆最壞的時(shí)間復(fù)雜度用O表示是多少？

最壞的情況是，每次將第i個(gè)元素放入堆中時(shí)，該元素都必須上移logi次，因此構(gòu)建最小堆的最壞時(shí)間復(fù)雜度是Log1 log2。。。Logn=Log1*2*。。。*n=對數(shù)（n！）。根據(jù)斯特林公式，n！近似等于（（2*pi*n）^（1/2））*（（n/E）^n）pi=3.1415926。E=2.718282，為常數(shù)。

那么n的階乘順序是n^n，也就是說，最壞情況下的時(shí)間復(fù)雜度是O（log（n^n））=O（nlogn）