最优二叉搜索树 - 时间复杂度
Optimal binary search Tree - TimeComplexity
所以真正让我绊倒的是，当我尝试计算这个算法的时间复杂度时，我很困惑，因为有 3 个循环，这让我相信操作是 O(n ^3) 但问题是中间循环随着外循环的增加而减少，而最内循环随着中间循环的减少而增加。我几乎猜测这是一个 O(n^2) 的整体算法，但由于 3 个嵌套循环，它似乎仍然是 O(n^3)。
当计算 运行 代码的操作次数时，我得到了 O(n^2) 和 O(n^3) 之间某处的计数，这使得它更加令人沮丧......
我尝试了一些东西，我想听听一些修复我的算法课程已经有一段时间了:)
The Sigma is for every loop. notice how it's becoming a multiply when
there is no dependency on the variable
所以真正让我绊倒的是，当我尝试计算这个算法的时间复杂度时，我很困惑，因为有 3 个循环，这让我相信操作是 O(n ^3) 但问题是中间循环随着外循环的增加而减少，而最内循环随着中间循环的减少而增加。我几乎猜测这是一个 O(n^2) 的整体算法，但由于 3 个嵌套循环，它似乎仍然是 O(n^3)。 当计算 运行 代码的操作次数时，我得到了 O(n^2) 和 O(n^3) 之间某处的计数，这使得它更加令人沮丧......
我尝试了一些东西，我想听听一些修复我的算法课程已经有一段时间了:)
The Sigma is for every loop. notice how it's becoming a multiply when there is no dependency on the variable