这里主要是练习一下用等差数列解决for循环的时间复杂度的一些问题

公式：

        等差数列求和公式：（首+尾）*项数/2 
        等差数列项数公式：（尾-首）/公差+1

有一组数组比如：1，3，5，7，9，这组数的首项就是1，尾项就是9，项数就是5（根据等差数列项数公式，尾项是9，首项是1，因为每个数字之间差2，所以公差就是2，得出项数是5）

下面看几个简单的题目，练习一下

题目：2016.for循环求和

1.暴力解法

http://ybt.ssoier.cn:8088/problem_show.php?pid=2016

#include<iostream>
using namespace std;
int main()
{int n; cin >> n;int sum = 0;for (int i = 1; i <= n; i++){sum += i;}cout << sum;return 0;
}

时间复杂度O(n)

2.等差数列前n项求和公式

#include<iostream>
using namespace std;
int main()
{int n; cin >> n;cout << ((1 + n) * n) / 2;//((1+n))*n：1是首项，n是尾项，*n是项数（(n-1)/1+1化简而来）return 0;
}

题目：1065.奇数求和

信息学奥赛一本通（C++版）在线评测系统

1.暴力解法

#include<iostream>
using namespace std;
int main()
{int m, n; cin >> m >> n;int sum = 0;for (int i = m; i <= n; i++){if (i % 2 == 1){sum += i;}}cout << sum;return 0;
}

时间复杂度：O(n-m+1)

2.优化解法

#include<iostream>
using namespace std;
int main()
{int m, n; cin >> m >> n;int sum = 0;if (m % 2 == 0)m++;//找到最小奇数for (int i = m; i <= n; i+=2)//从最小奇数开始循环{sum += i;}cout << sum;return 0;
}

思想：找到m~n范围内最小奇数（如果m不为奇数，m++后m就为最小奇数），然后从i为最小的奇数开始循环，每次迭代增加2(i+=2)时，i都是奇数。

3.等差数列前n项求和公式

#include<iostream>
using namespace std;
int main()
{int m, n; cin >> m >> n;if (m % 2 == 0)m++;//如果是偶数就m++变为范围内最小奇数if (n % 2 == 0)n--;//如果是偶数就m--变为范围内最大奇数cout << ((m + n) * ((n - m) / 2 + 1)) / 2;//(m+n)：首项+尾项//((n - m) / 2 + 1))：项数return 0;
}

题目：2018.输出奇偶数之和

信息学奥赛一本通（C++版）在线评测系统

#include<iostream>
using namespace std;
int main()
{int n; cin >> n;//last：尾项int last = n, sum_odd = 0, sum_even = 0;if (n % 2 == 0)last = n - 1;//如果是偶数的话就n-1，尾项变为奇数。如果是奇数尾项不变还是nsum_odd = (1 + last)* ((n - 1) / 2 + 1) / 2;//等差数列求和公式if (n % 2 == 1)last = n - 1;//如果是奇数的话就n-1，尾项变为偶数。如果是偶数尾项不变还是nelse last = n;sum_even = (2 + last) * ((n - 2) / 2 + 1) / 2;//等差数列求和公式cout << sum_even << " " << sum_odd;return 0;
}

有很多题目可以用数学的公式来解答，大大减小了时间复杂度