Сложность времени следующего кода ..?

Question

Меня смущает сложность времени следующего фрагмента кода ...

i = 0

   //first row
   if(board[i][0] == win && board[i][1] == win && board[i][2] == win)
      return win;

   //second row
   if(board[i+1][0] == win && board[i+1][1] == win && board[i+1][2] == win)
      return win;

   //third row
   if(board[i+2][0] == win && board[i+2][1] == win && board[i+2][2] == win)
      return win;

   //first col
   if(board[0][i] == win && board[1][i] == win && board[1][i] == win)
      return win;

   //second col
   if(board[0][i+1] == win && board[1][i+1] == win && board[2][i+1] == win)
      return win;

   //third col
   if(board[0][i+2] == win && board[1][i+2] == win && board[2][i+2] == win)
      return win;

      //first diag
   if(board[i][i] == win && board[i+1][i+1] == win && board[i+2][i+2] == win)
      return win;

   //second diag
   if(board[i+2][i] == win && board[i+1][i+1] == win && board[i][i+2] == win)
      return win;

Answer 1

Он будет работать в постоянное время, т.е. O (1), предполагая, что доска [M] [N] будет двумерным массивом.

Answer 2

Это, очевидно, ловушечный вопрос, чтобы увидеть, поняли ли вы понятие сложности времени.

Сложность времени измеряет порядок величины, который необходим алгоритму, если он применяется к все большему и большему входу.Ваш пример зависит только от постоянного числа входов, поэтому другие правильно сказали O (1).По сути, это означает, что сложность времени не является правильным инструментом для измерения его эффективности, качества или чего-либо еще.

Answer 3

O (1) - ни итераций, ни рекурсии.

Answer 4

Как показывают другие ответы, это O (1). Но это не считается хорошей практикой кодирования. Вы можете использовать цикл для его обобщения.

Answer 5

Как вы там показали, это O (1), потому что в нем нет переменных-граней.Выполнение всегда будет занимать одно и то же время.

Если вы поместите его в цикл, где i переходит от 0 до n-1, то он будет иметь O (n), то есть линейную сложность.Если вы удвоите размер n, вы примерно удвоите время выполнения.