时间戳

首页 > 解决方案 > 如何将给定的级数表达式简化为代数表达式？

big-o - 如何将给定的级数表达式简化为代数表达式？

问题描述

我需要将给定的级数表达式简化为代数表达式，而不需要求和。

然后我必须用 Big O Notation 来表达代数表达式的表现。

我主要对第一部分感到困惑。我不太清楚如何将级数表达式解释为代数表达式。一个解释会很棒！谢谢。

算法：

for ( j = 0; j < n; j++ )

{

 for ( k = j; k < n; k++ )

 {



 }

}
will result in a number of iterations of given by the expression:

 = n + (n-1) + (n-2) + (n-3) + ........ + (n - n)

标签： big-o

解决方案

因为j=0有 的n值k。因为j=1有 的n-1值k。因为j=2有 的n-2值k。...因为j=n-2有. 因为有 的值。n-(n-2)kj=n-1n-(n-1)k

因此，内部循环将具有：

n + (n-1) + ... + (n-(n-2)) + (n-(n-1))

迭代。

尽管数学家使用了许多技术，但没有将表达式转换为封闭形式的通用方法，即转换为具有固定操作数 , , 的代数表达式+（-意味着*这个/数字不依赖于参数n）。

因此，您基本上必须提前了解一些众所周知的转换，并尽可能将它们组合起来。

在上面的示例中，我们可以将表达式重写为：

sum_{j=0}{n-1} (n - j)

然后像这样操作它：

sum_{j=0}^{n-1} (n - j) = Σ(n-j)                     ; 0 ≤ j ≤ n-1
                        = Σn - Σj                    ; regroup
                        = n*n - (n-1)n/2             ; see below
                        = n(n+1)/2                   ; n is common factor

这里众所周知的公式是我用来替换的公式Σj，你会在很多地方找到它的解释。第一个替换Σn = n*n是微不足道的，因为我们正在添加n自身n时间。

推荐阅读