时间戳

首页 > 解决方案 > 如何计算以下伪代码的封闭形式？

c++ - 如何计算以下伪代码的封闭形式？

问题描述

我需要帮助解决以下问题：

分析以下程序片段的运行时间并编写伪代码（在 C++ 中），它将输出 this 的值，但以恒定时间运行。您可以假设在程序的前面给出了 n。

 sum = 0
 for i from 1 to n-1 do
   for j from i to n*n do
     sum = sum + i

我要做什么：我知道以下程序片段的时间复杂度为 O(n 2 )，并且：

sum = n*n*(n)*(n-1)/2-(n-1)*n*(2*(n-1)+1)/6+(n-1)*n/2;

我不确定如何将其转换为伪代码格式。任何帮助将不胜感激，谢谢！

标签： c++algorithmpseudocode

解决方案

 sum <- n*n*(n)*(n-1)/2-(n-1)*n*(2*(n-1)+1)/6+(n-1)*n/2

就这样。当您知道封闭式公式时，就不需要循环了。

用这样的公式计算具有恒定的时间复杂度

推荐阅读