如何发现程序的时间复杂性

Question

我找到了这段代码来计算字符串的切割"字符串切割的动态编程练习"这个代码可以帮助我找到它的时间复杂性：

public static int findMinCutCost2(int[] m, int n) {
if (m.length == 0)
return 0;
if (m.length == 1)
return n;
float half = n / 2f;
int bestIndex = 0;
for (int i = 1; i < m.length; i++) {
if (Math.abs(half - m[bestIndex]) > Math.abs(half - m[i])) {
bestIndex = i;
}
}
int cl = 0, cr = 0;
if (bestIndex > 0) {
int[] ml = Arrays.copyOfRange(m, 0, bestIndex);
int nl = m[bestIndex];
cl = findMinCutCost2(ml, nl);
}
if (bestIndex < m.length - 1) {
int[] mr = Arrays.copyOfRange(m, bestIndex + 1, m.length);
int nr = n - m[bestIndex];
for (int j = 0; j < mr.length; j++) {
mr[j] = mr[j] - m[bestIndex];
}
cr = findMinCutCost2(mr, nr);
}
return n + cl + cr;
}

Answer 1

总复杂性为O(nlog(n))。为什么：因为对于每个数组，您实际上将其分为两部分，每个部分都有n次迭代。存在最高日志(n(级别，并且在每个级别上都有n循环。因此总复杂度为O(nlog(n((。

为了简单起见，假设数组总是一分为二。如果不是即使是一半，它也将处理第一部分(m.length-bestIndex(和第二部分部分(最佳索引到长度(，其在总阵列大小->n。

n              -> n loop
/ 
/   
n/2   n/2         -->n/2 + n/2 loop
/     ...
/   
n/4   n/4