斐波那契数
// 斐波那契数1 --- 递归 性能差
// O(2^n)
public static int fib1(int n) {
if (n <= 1) return n;
return fib1(n - 1) + fib1(n - 2);
}
// 斐波那契数2 --- 非递归 性能比第一种好
// O(n)
public static 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;
}
// 斐波那契数3
public static int fib3(int n) {
if (n <= 1) return n;
int first = 0;
int second = 1;
while (n-- > 1) {
second += first;
first = second - first;
}
return second;
}
public static void main(String[] args) {
// 斐波那契数1
// System.out.println(fib1(0));
// System.out.println(fib1(1));
// System.out.println(fib1(2));
// System.out.println(fib1(3));
// System.out.println(fib1(4));
// System.out.println(fib1(5));
// 斐波那契数2 --- 性能比第一种好
// System.out.println(fib2(0));
// System.out.println(fib2(1));
// System.out.println(fib2(2));
// System.out.println(fib2(3));
// System.out.println(fib2(4));
// System.out.println(fib2(5));
// 斐波那契数3
// System.out.println(fib3(0));
// System.out.println(fib3(1));
// System.out.println(fib3(2));
// System.out.println(fib3(3));
// System.out.println(fib3(4));
// System.out.println(fib3(5));
int n = 45;
// 测试fib1消耗时间
Times.test("fib1", new Task() {
public void execute() {
System.out.println(fib1(n));
}
});
// 测试fib2消耗时间
Times.test("fib2", new Task() {
public void execute() {
System.out.println(fib2(n));
}
});
}
1、什么是算法
◼ 算法是用于解决特定问题的一系列的执行步骤
// 计算a和b的和
- (int)plus:(int)a b:(int)b {
return a + b;
}
// 计算 1+2+3+...+n 的和
- (int)sum:(int)n {
int result = 0;
for (int i = 1; i<= n; i++) {
result += I;
}
return result;
}
◼ 使用不同算法，解决同一个问题，效率可能相差非常大
比如:求第 n 个斐波那契数(fibonacci number)
2、如何评判一个算法的好坏？
// 计算 1+2+3+...+n 的和
- (int)sum:(int)n {
int result = 0;
for (int i = 1; i<= n; i++) {
result += I;
}
return result;
}
// 计算 1+2+3+...+n 的和
- (int)sum1:(int)n {
return (1 + n) * n / 2;
}
◼ 如果单从执行效率上进行评估，可能会想到这么一种方案
比较不同算法对同一组输入的执行处理时间
这种方案也叫做:事后统计法
◼ 上述方案有比较明显的缺点
执行时间严重依赖硬件以及运行时各种不确定的环境因素
必须编写相应的测算代码
测试数据的选择比较难保证公正性
◼ 一般从以下维度来评估算法的优劣
正确性、可读性、健壮性(对不合理输入的反应能力和处理能力)
时间复杂度(time complexity):估算程序指令的执行次数(执行时间)
空间复杂度(space complexity):估算所需占用的存储空间
3、大O表示法(Big O)
◼一般用大O表示法来描述复杂度，它表示的是数据规模 n 对应的复杂度
◼ 忽略常数、系数、低阶
9 >> O(1)
2n + 3 >> O(n)
n2 + 2n + 6 >> O(n2)
4n3 + 3n2 + 22n + 100 >> O(n3)
写法上，n3 等价于 n^3
◼ 注意:大O表示法仅仅是一种粗略的分析模型，是一种估算，能帮助我们短时间内了解一个算法的执行效率
4、对数阶的细节
◼ 对数阶一般省略底数
log2 n = log2 9 * log9 n
◼ 所以log2 n，log9 n统称为 logn
5、常见的复杂度
常见的复杂度
6、数据规模较小时
7、数据规模较大时
8、实例讲解时间复杂度
test1 时间复杂度 O(1)
- (void)test1:(int)n {
if (n > 10) {
NSLog(@"n > 10");
} else if (n > 5) { // 2
NSLog(@"n > 5");
} else {
NSLog(@"n <= 5");
}
for (int i = 0; i < 4; i++) {
NSLog(@"test1");
}
}
test2 时间复杂度 O(n)
- (void)test2:(int)n {
// 1 + 3n (指令执行条数)
// O(n)
for (int i = 0; i < n; i++) {
NSLog(@"test");
}
}
test3 时间复杂度 O(n^2)
- (void)test3:(int)n {
// 1 + 2n + n * (1 + 3n) (指令执行条数)
// 1 + 2n + n + 3n^2
// 3n^2 + 3n + 1
// O(n^2)
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
NSLog(@"test");
}
}
}
test4 时间复杂度 O(n)
- (void)test4:(int)n {
// 1 + 2n + n * (1 + 45) (指令执行条数)
// 1 + 2n + 46n
// 48n + 1
// O(n)
for (int i = 0; i < n; i++) {
for (int j = 0; j < 15; j++) {
NSLog(@"test");
}
}
}
test5 时间复杂度 O(logn)
- (void)test5:(int)n {
// 执行次数 = log2(n)
// O(logn)
while ((n = n / 2) > 0) {
NSLog(@"test");
}
}
test6 时间复杂度 O(logn)
- (void)test6:(int)n {
// log5(n)
// O(logn)
while ((n = n / 5) > 0) {
NSLog(@"test");
}
}
test7 时间复杂度 O(nlogn)
- (void)test7:(int)n {
// 1 + 2*log2(n) + log2(n) * (1 + 3n)
// 1 + 3*log2(n) + 3 * nlog2(n)
// O(nlogn)
for (int i = 1; i < n; i = i * 2) {
// 1 + 3n
for (int j = 0; j < n; j++) {
NSLog(@"test");
}
}
}
多个数据规模的情况
- (void)test8:(int)n k:(int)k {
for (int i = 0; i < n; i++) {
NSLog(@"test8 %d",i);
}
for (int i = 0; i < k; i++) {
NSLog(@"test8 %d",i);
}
}
时间复杂度为 O(n + k)
9、求第n个斐波那契数(fibonacci number)
求第n个斐波那契数(fibonacci number)
摘自百度百科的解释 斐波那契数
斐波那契数，亦称之为斐波那契数列（意大利语： Successione di Fibonacci)，又称黄金分割数列、费波那西数列、费波拿契数、费氏数列，指的是这样一个数列：1、1、2、3、5、8、13、21、……在数学上，斐波那契数列以如下被以递归的方法定义：F0=0，F1=1，Fn=Fn-1+Fn-2（n>=2，n∈N*） ，用文字来说，就是斐波那契数列由 0 和 1 开始，之后的斐波那契数列系数就由之前的两数相加。
算法一
// 递归
- (int)fib1:(int)n {
if (n <= 1) {
return n;
}
// Fn = Fn-1 + Fn-2（n >= 2，n∈N*）
return [self fib1:n - 1] + [self fib1:n - 2];
}
算法二
// 直接求值
- (int)fib2:(int)n {
if (n <= 1) {
return n;
}
int first = 0;
int second = 0;
// Fn = Fn-1 + Fn-2
for (int i = 1; i < n; i++) {
second += first;
first = second - first;
}
return second;
}
TimeTool.m
/// 计算执行完 block 所需花费时间
+ (void)calculateTimeWithTitle:(NSString *)title operationBlock:(void(^)(void))operationBlock {
NSDateFormatter *formatter = [[NSDateFormatter alloc] init];
[formatter setDateFormat:@"YYYY-MM-dd HH:mm:ss:mmm"];
NSDate *startDate = [NSDate date];
NSString *currentTimeString = [formatter stringFromDate:startDate];
NSLog(@"%@ start, time = %@",title,currentTimeString);
if (operationBlock) {
operationBlock();
}
NSDate *endDate = [NSDate date];
currentTimeString = [formatter stringFromDate:endDate];
NSLog(@"%@ end, time = %@",title,currentTimeString);
NSLog(@"%@ 耗时:%f second",title,[endDate timeIntervalSince1970] - [startDate timeIntervalSince1970]);
}
比较两个算法的时间
- (void)viewDidLoad {
[super viewDidLoad];
int n = 35;
// fib1
[TimeTool calculateTimeWithTitle:@"fib1" operationBlock:^{
[self fib1:n];
}];
// fib2
[TimeTool calculateTimeWithTitle:@"fib2" operationBlock:^{
[self fib2:n];
}];
}
n = 35时
经过大量测试，发现当 n < 35的时候，两个算法的执行时间相差不大，但是随着n的增加，相差时间越来越明显了。
两个算法的时间复杂度分析
fib1函数的时间复杂度分析
fib1的时间复杂度为O(2n)
fib2函数的时间复杂度分析
循环n次，所以时间复杂度为O(n)
◼ 他们的差别有多大？
如果有一台1GHz的普通计算机，运算速度109 次每秒( n 为 64 )
O(n) 大约耗时 6.4 ∗ 10-9 秒
O(2n) 大约耗时 584.94 年
有时候算法之间的差距，往往比硬件方面的差距还要大
10、算法的优化方向
◼ 用尽量少的存储空间
◼ 用尽量少的执行步骤(执行时间)
◼ 根据情况，可以
空间换时间
时间换空间
11、多个数据规模的情况
O(n + k)
12、更多知识
◼ 更多复杂度相关的知识，会在后续讲解数据结构、算法的过程中穿插
最好、最坏复杂度
均摊复杂度
复杂度震荡
平均复杂度
......
13、leetcode
◼ 一个用于练习算法的好网站
leetcode.com
leetcode-cn.com
◼ 斐波那契数
fibonacci
