題目鏈接：點擊這里
#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;
}
算法效率如何度量？
- 事后統(tǒng)計
- 事前分析
步驟：
- 找到執(zhí)行次數(shù)最多的語句
- 計算語句執(zhí)行次數(shù)的數(shù)量級
- 用大О來表示結果
分析下面程序的功能，并計算時間復雜度桥嗤？
#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;
}
并列：總復雜度等于量級最大的那段代碼的復雜度。
嵌套：嵌套代碼的復雜度等于嵌套內(nèi)外代碼復雜度的乘積往踢。
