Python TicTacToe 函数的时间复杂度

Question

def TicTacToe():
    board = [['S' for i in range(3)] for j in range(3)]
    BoardState(board)

    for i in range(8):
        if(i % 2 == 0):
            print("Enter the position player 1: ")
            a = int(input())
            b = int(input())
            if(board[a - 1][b - 1] == 'S'):
                board[a - 1][b - 1] = 1
            else:
                print("Invalid Input, game over")
                return
        else:
            print("Enter the position player 2: ")
            a = int(input())
            b = int(input())
            if(board[a - 1][b - 1] == 'S'):
                board[a - 1][b - 1] = 0
            else:
                print("Invalid input, game over")
                return
                
        BoardState(board)
        
        if(board[0][0] == 1 and board[1][1] == 1 and board[2][2] == 1):
            return "Player 1 wins"
        if(board[0][0] == 0 and board[1][1] == 0 and board[2][2] == 0):
            return "Player 2 wins"
        if(board[0][2] == 1 and board[1][1] == 1 and board[2][0] == 1):
            return "Player 1 wins"
        if(board[0][2] == 0 and board[1][1] == 0 and board[2][0] == 0):
            return "Player 2 wins"
        if(CheckState(board) == 0):
            return "game over"
        
    return "Draw"

def CheckState(board):        
    for x in range(3):
        if board[x][0] == board[x][1] == board[x][2] != 'S' \
        or board[0][x] == board[1][x] == board[2][x] != 'S':
            return 0
        
def BoardState(board):
    for i in range(3):
        for j in range(3):
            print(board[i][j], end = ' ')
        print("\n")    


TicTacToe();

这是我为井字游戏写的一段不太干净的代码。它的时间复杂度是多少？

该程序由 3 个函数组成，我想计算它们的复杂度。它会是 O(1) 吗，因为输入大小已经固定，它不会随用户输入而变化吗？

Answer 1

Would it be O(1) as the input size is already fixed it doesn't vary with whatever the user inputs?

是的，完全正确。所有循环都有固定的迭代次数。

Answer 2

我认为你实际上在谈论两个不同的问题：第一个是充当“裁判”的程序，类似于你上面的程序。第二个是与人类玩家（或其他程序）对战的程序。

对于复杂性，请考虑 N x N 井字棋盘的情况。在那种情况下，我认为第一个问题的复杂度是 O(N)，而第二个问题的复杂度是 N 的指数。

Python TicTacToe 函数的时间复杂度

Time Complexity of Python TicTacToe function

python

time-complexity

tic-tac-toe