[数据结构与算法]数据结构与算法第一阶段

1.

1.1斐波那契数

#include <iostream>
using namespace std;

int fib1(int n)
{
	if (n <= 1) return n;
	return fib1(n - 1) + fib1(n - 2);
}
int fib2(int n)
{
	if (n <= 1) return n;
	int first = 0;
	int second = 1;
	for (int i = 0; i < n - 1; i++)
	{
		int sum = first + second;
		first = second;
		second = sum;
	}
	return second;
}
int main()
{
	cout << fib1(0) << endl;
	cout << fib1(1) << endl;
	cout << fib1(2) << endl;
	cout << fib1(3) << endl;
	cout << fib1(4) << endl;
	cout << fib1(5) << endl;
	cout << fib2(64) << endl;
	system("pause");
	return 0;
}

1.2算法的评估

• 正确性、可读性、健壮性
• 时间复杂度
• 空间复杂度

1.3时间复杂度的估算