Почему O (n) занимает больше времени, чем O (n ^ 2)? - PullRequest
Новая
       17

Почему O (n) занимает больше времени, чем O (n ^ 2)?

0 голосов
/ 25 мая 2018

У меня проблема с LeetCode:

Если задана матрица M x N, вернуть True, если и только если матрица является теплицевой.

Матрица имеет значение Теплиц , есликаждая диагональ от верхнего левого до нижнего правого имеет один и тот же элемент.

Мое решение (Swift): 

func isToeplitzMatrix(_ matrix: [[Int]]) -> Bool {
    if matrix.count == 1 { return true }

    for i in 0 ..< matrix.count - 1 {
        if matrix[i].dropLast() != matrix[i + 1].dropFirst() { return false }
    }

    return true
}

Как я понял обозначение Big O, сложность времени моего алгоритма равна O(n), в то время как верхние ответы LeetCode 'O (n ^ 2).

Пример верхних ответов: 

func isToeplitzMatrix(_ matrix: [[Int]]) -> Bool {
    for i in 0..<matrix.count-1 {
      for j in 0..<matrix[0].count-1 {
          if (matrix[i][j] != matrix[i+1][j+1]) {
              return false;
          }
      }
    }

     return true;
}

Тем не менее, мой алгоритм занимает 36 мс (согласно LeetCode), в то время как topответ занимает 28 мс.

Когда я прокомментировал if matrix.count == 1 { return true }, потребовалось еще больше времени - 56 мс.

1 Ответ

0 голосов
/ 25 мая 2018

Ваша временная сложность для функции также O (n ^ 2), потому что вызов функции dropLast равен O (n).

Редактировать: Также упоминается Rup и melpomene, сравнение массивов также принимаетсложность до O (n ^ 2).

Кроме того, обозначение Big O описывает, как алгоритм масштабируется в ответ на n, количество данных.Для краткости отнимает любые константы.Поэтому алгоритм с O (1) может быть медленнее, чем алгоритм с O (n ^ 3), если входные данные достаточно малы.

...