Является ли сложность этого кода O (n^2) или O (n^2 * n^(1/2))?

Question

Я думал, что сложность будет O (n^2). Я ошибаюсь? Если да, не могли бы вы объяснить, почему?

public int countXs(char[][] m) 


{ 
    int rows = m.length, cols = m[0].length; 
    int r = 0, c = 0, count = 0; 
    while (r < rows || c < cols) 
    { 
     count += r; 
     while (r < rows && m[r][c] == 'x') 
     { 
     count++; 
     r++; 
     } 
     c++; 
    } 
    return count; 
    } 

Answer 1

Во-первых, ваш код может произойти сбой из-за arrayIndexOutofBound с c индексом.

Далее, когда вы вкладываете сложность во времени, во-первых, вам нужно определить, что такое n. Обычно n указывает размер ввода, в этом случае n является размером 2-мерного массива.

Итак, вам нужно настроить формулу на временную сложность и указать наихудший случай вашего кода, чтобы найти сложность по времени. Предположим, что массив m равен pxq (p + q = n), и мы обозначаем O(1) = 1.

T(n) = Sum(i->max(p, q)) {1 + sum(j->p)(1)} 
    = max(p,q) + sum(i->max(p,q)){p} 
    = max(p, n-p) + sum(i-> max(p, n-p)) {p} 
    = max(p, n-p) + p(n-p) 

на основе Cauchy inequality:

4*ab <= (a+b)^2 we have: p(n - p) < (p + n - p)^2 /4 = n^2/4 

Итак:

T(n) <= n + n^2/4 = O(n^2) . Q.E.D 

Подробнее: http://en.wikipedia.org/wiki/Time_complexity