как найти временную сложность программы?

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 итераций .Существует максимум log (n ) уровень и на каждом уровне есть n loop .таким образом, общая сложность составляет O (nlog (n)) .

Для простоты предположим, что массив всегда делится на половину.Если даже не половина, он обработает первую часть (m.length-bestIndex) и вторую часть (bestIndex to length), которые в общем размере массива-> n.

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