时间戳

首页 > 解决方案 > 这两种方法在 Python 中如何具有不同的时间复杂度？

python - 这两种方法在 Python 中如何具有不同的时间复杂度？

问题描述

我正在尝试解决Leetcode 单词搜索问题。

我有两个解决方案对我来说是相同的，尽管其中一个在 Time Limit Exceeded 中返回。

我阅读了有关此的所有资源，但无法理解幕后发生的事情。

具有优化时间复杂度的解决方案 1：

class Solution(object):
    def bfs(self, position, visited, board, word):
        # print(position)
        if not word:
            return True

        destination = [(-1,0), (1,0), (0,1), (0,-1)]
        res = False
        for x,y in destination:
            new_postion_x, new_postion_y = position[0] + x, position[1] + y
            if (0<= new_postion_x < len(board)) and (0 <= new_postion_y < len(board[0])) and (new_postion_x, new_postion_y) not in visited:
                if board[new_postion_x][new_postion_y] == word[0]:
                    new_visited = visited.copy()
                    new_visited[(new_postion_x,new_postion_y)] = 1
                    res = res or self.bfs((new_postion_x, new_postion_y), new_visited, board, word[1:])
        return res

    def exist(self, board, word):
        for i in xrange(len(board)):
            for j in xrange(len(board[0])):
                if board[i][j] == word[0]:
                    t = self.bfs((i,j), {(i,j): 1}, board, word[1:])
                    if t:
                        return True
        return False

解决方案二在执行大输入时返回 TLE：

class Solution(object):
    def bfs(self, position, visited, board, word):
        print(position)
        if not word:
            return True

        destination = [(-1,0), (1,0), (0,1), (0,-1)]
        res = False
        for x,y in destination:
            new_postion_x, new_postion_y = position[0] + x, position[1] + y
            if (0<= new_postion_x < len(board)) and (0 <= new_postion_y < len(board[0])) and (new_postion_x, new_postion_y) not in visited:
                if board[new_postion_x][new_postion_y] == word[0]:
                    new_visited = visited.copy()
                    new_visited[(new_postion_x,new_postion_y)] = 1
                    t = self.bfs((new_postion_x, new_postion_y), new_visited, board, word[1:])
                    res = res or t
        return res

    def exist(self, board, word):
        for i in xrange(len(board)):
            for j in xrange(len(board[0])):
                if board[i][j] == word[0]:
                    t = self.bfs((i,j), {(i,j): 1}, board, word[1:])
                    if t:
                        return True
        return False

标签： pythonalgorithmdata-structurestime-complexity

解决方案

关键线在这里：

res = res or self.bfs((new_postion_x, new_postion_y), new_visited, board, word[1:])

一旦res变为True，此行将永远不会再次执行，因为不需要计算self.bfs()之后的表达式。or这称为短路。
因此，一旦找到解决方案，您就不会再进行任何递归调用并快速将True所有方法返回到顶部。写这个的一种等效方式，可能会澄清它，将是：

if not res:
    res = self.bfs(...)

在另一个解决方案中：

t = self.bfs((new_postion_x, new_postion_y), new_visited, board, word[1:])
res = res or t

即使不再需要它，它也会始终调用，即使已经找到解决方案，它也会始终搜索整个图形。self.bfs()

推荐阅读