算式求和 - C++ 代码实现

**题目描述:**

设 /(f(x)/) 表示 /(1/sim x/) 中所有奇数之和。

请计算出 /(S(n) = f(1) + f(2) + f(3) + //cdots + f(n)/)。

**输入格式:**

一个正整数 /(n/)。

**输出格式:**

一个正整数 /(S(n)/)，表示计算结果。

样例

样例输入 #1

样例输出 #1

样例输入 #2

样例输出 #2

解题思路

我们可以通过两个循环来计算 /(S(n)/)：

外层循环遍历 /(1/) 到 /(n/) 的每个数 /(i/)。
内层循环遍历 /(1/) 到 /(i/) 的所有奇数，并将其累加到 /(sum/) 中。

代码实现

#include <iostream>/nusing namespace std;/n/nint main() {/n    int n;/n    cin >> n;/n    /n    long long sum = 0;/n    for (int i = 1; i <= n; i++) {/n        for (int j = 1; j <= i; j += 2) {/n            sum += j;/n        }/n    }/n    /n    cout << sum << endl;/n    /n    return 0;/n}/n

时间复杂度和空间复杂度

该算法的时间复杂度为 /(O(n^2)/)，因为我们使用了两个嵌套循环。空间复杂度为 /(O(1)/)，因为我们只使用了常数个额外空间。

优化

我们可以通过以下方法来优化算法：

使用公式 /(f(x) = x^2/) 来计算 /(f(x)/)。
使用等差数列的求和公式来计算 /(S(n)/)。

优化后的算法时间复杂度为 /(O(1)/)，空间复杂度也为 /(O(1)/)。

C++ 算法题：算式求和 - 解题思路与代码实现