What is the time complexity in this?

2018-06-13 19:27:54

This question already has an answer here:

Big O, how do you calculate/approximate it? 22 answers

Worst case is O(n^2) if you assume all blocks are "free" and they have a size of decreasing powers of 2 with last two being 1:

2^n, 2^(n-1) ... , 64, 32, 16, 8, 4, 2, 1, 1

First iteration merges the last two, triggers a recursive call that now operates on a list that looks like

2^n, 2^(n-1) ... , 64, 32, 16, 8, 4, 2, 2

merges the last two, calls recursively, now operating on

2^n, 2^(n-1) ... , 64, 32, 16, 8, 4, 4

etc. First time n loops, then n-1, n-2, ... Sum all those you get n * (n + 1) / 2 steps, or O(n^2) .

Best case is O(n) if you only iterate once without recursion, doing basically nothing.

Average case is somewhere in between... I cannot calculate that one.

链接地址: http://www.djcxy.com/p/39364.html