题目链接：点击这里
#include<iostream>
using namespace std;
int main()
{
int n;
cin >> n;
int sum = 0;
for(int i = 1; i <= n; i++)
{
int fac = 1; //求i!
for(int j = 1; j <= i; j++)
fac *= j;
sum += fac; //累加i!
}
cout << sum << endl;
return 0;
}
#include<iostream>
using namespace std;
int main()
{
int n;
cin >> n;
int sum = 0, fac = 1;
for(int i = 1; i <= n; i++)
{
fac *= i; //求i!
sum += fac; //累加i!
}
cout << sum << endl;
return 0;
}
算法效率如何度量？
- 事后统计
- 事前分析
步骤：
- 找到执行次数最多的语句
- 计算语句执行次数的数量级
- 用大О来表示结果
分析下面程序的功能，并计算时间复杂度？
#include<iostream>
using namespace std;
int main()
{
int n;
cin >> n;
int sum = 0;
for(int i = 1; i <= n; i++)
sum += i * i * i;
cout << sum << endl;
return 0;
}
对比下面两个程序的功能，分别计算时间复杂度？
#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 << endl;
return 0;
}
#include<iostream>
using namespace std;
int main()
{
int n;
cin >> n;
int sum = (n + 1) * n / 2;
cout << sum << endl;
return 0;
}
计算下面三个程序的结果及其时间复杂度？
#include<iostream>
using namespace std;
int main()
{
int n;
cin >> n;
int a = 0;
for(int i = 0; i < n; i++)
{
a++;
}
for(int i = 0; i < n; i++)
{
a--;
}
cout << a << endl;
return 0;
}
#include<iostream>
using namespace std;
int main()
{
int n;
cin >> n;
int a = 0;
for(int i = 0; i < n; i++)
{
a--;
for(int i = 0; i < n; i++)
{
a++;
}
}
cout << a << endl;
return 0;
}
#include<iostream>
using namespace std;
int main()
{
int n;
cin >> n;
int a = 0;
for(int i = 0; i < n; i++)
{
a--;
for(int i = 0; i < n; i++)
{
a++;
}
}
int sum = 0;
for(int i = 1; i <= a; i++)
sum += i;
cout << sum << endl;
return 0;
}
并列：总复杂度等于量级最大的那段代码的复杂度。
嵌套：嵌套代码的复杂度等于嵌套内外代码复杂度的乘积。
