如果问题大小为n，并且每次算法将问题大小减少一半，我认为复杂度为O (n log n)，例如归并排序。所以，基本上你运行了n次(log n)算法(比较)…
现在的问题是，如果我有一个大小为n的问题，我的算法能够在一次运行中将大小减少一半，每次运行需要O(n log n)这种情况下的复杂度是多少?
如果问题在大小为n时需要n步，加上当n> 1时在大小为(n/2)的地方额外运行一次，那么总共需要O(n)时间:n + n/2 + n/4 +…=~ 2n = 0 (n).
同样，如果每次运行花费O(n log n)时间，并且当n> 1时，在大小为floor(n/2)时额外运行一次，则总时间为O(n log n)。
由于问题的大小在每次迭代中减半，并且在每一级所花费的时间为n log n，因此递归关系为
T(n) = T(n/2) + n log n
应用主定理，
与T(n) = a T(n/b) + f(n)相比，我们有a=1和b=2。
因此n <一口>日志<子> b = n <一口>日志<子> 2 1> = 1.
因此f (n) = n o (log n)> n <一口>日志<子> b 。
应用主定理得到T(n) = Θ(f(n)) = Θ(n log n)
因此复杂度为T(n) = Θ(n log n)。注释后编辑:
如果每次运行时问题的大小减半，则需要log(n)次运行才能完成。因为每次运行需要n*log(n)的时间，所以你需要log(n)乘以n*log(n)的运行。总复杂度为:
O(n log(n)^2)
如果我没有误解这个问题，第一次运行完成的时间(与)nlogn成正比。第二次运行只剩下n/2，因此在n/2log(n/2)内完成，以此类推。
对于大n，这是你在分析时间复杂度时假设的，log(n/2) = (logn - log2)将被替换为logn。
对"所有"步骤求和:Log (n) * (n + n/2 + n/4…)= 2n Log (n)，即时间复杂度nlogn
换句话说:时间复杂度与您的第一步/基本步骤相同，所有其他步骤加在一起"仅"贡献相同的数量
我很确定它等于O(n^2 log n)你创建一个几何级数n + n/2 + n/4 +…= 2n(对于较大的n)，但是忽略系数，只得到n。
这很好，除非你的意思是内部的nlogn与外部的n是相同的n值。
编辑:我认为OP在这里的意思是每次运行内部nlogn也会被处理。换句话说，
nlogn + n/2 logn/2 + n/4 logn/4 +…+ n/2^(n-1) log n/2^(n-1)
如果是这种情况，那么需要考虑的一件事是在某个点
2^(n-1)> n
在这一点上，日志中断(因为0到1之间的数字的对数是负的)。但是，你真的不需要日志，因为在这些迭代中只有一次操作。从这里开始，你只需要加1。
发生在log n/log 2。因此，对于第一个log n/log 2次迭代，我们得到了上面的和，之后它只是一个1的和。
nlogn + n/2 logn/2 + n/4 logn/4 +…+ n/2^(log n/log 2) log n/2^(log n/log 2) + 1 + 1 + 1 + 1…(n - log n/log 2)乘以