网站建设项目策划书范文,ppt模板下载免费版课件,wordpress装模板,网站建设 检查 通报一、算法好坏的度量 【事前分析法】 算法设计好后#xff0c;根据算法的设计原理#xff0c;只要问题规模确定#xff0c;算法中基本语句执⾏次数和需求资源个数 基本也就确定了。 ⽐如求1 2 3 ... n − 1 n #xff0c;可以设计三种算法#xff1a;
算法A#xff…一、算法好坏的度量 【事前分析法】 算法设计好后根据算法的设计原理只要问题规模确定算法中基本语句执⾏次数和需求资源个数 基本也就确定了。 ⽐如求1 2 3 ... n − 1 n 可以设计三种算法
算法A需要开辟⼀个⼤⼩为N 的空间。
const int N 1e5 10;
int a[N];
int sum(int n)
{// 先把 1 ~ n 存起来 for(int i 1; i n; i){a[i] i;}// 循环逐个数字相加 int ret 0;for(int i 1; i n; i){ret a[i];}return ret;
}
算法B不需要开辟空间直接求和。需要循环n 次ret n 语句会执⾏n 次⽽且随着问题规模的增⻓执⾏次数也会增⻓。
int sum(int n)
{// 循环逐个数字相加 int ret 0;for (int i 1; i n;
i) {ret i;}return ret;
}
算法C不论问题规模为多少 语句只会执⾏1 次。
int sum(int n)
{// 利⽤求和公式 return (1 n) * n / 2;
}
综上所述时间和空间的消耗情况就是我们度量⼀个算法好坏的标准也就是时间复杂度和空间复杂度。
二、时间复杂度
时间复杂度 在计算机科学中算法的时间复杂度是⼀个函数式 它定量描述了该算法的运⾏时间。这个函数式计算了程序中语句的执⾏次数。
案例计算⼀下fun中count语句总共执⾏了多少次
void fun(int N)
{ int count 0; for(int i 0; i N; i) { for(int j 0; j N; j) { count; // 执⾏次数是 n*n也就是 n^2 } } for(int k 0; k 2 * N; k) {count; // 执⾏次数是 2*n } int M 10; while(M--) { count; // 执⾏次数 10 }
}
fun 函数count 语句的总执⾏次数 T (N) N 2 2 × N 10 • 当N 10 时T (N) 100 20 10 130 • 当N 100 时T (N) 10000 200 10 10210 • 当N 1000 时T (N) 1000000 2000 10 1002010 • 当N 10000 时T (N) 100000000 20000 10 100020010 推导⼤O渐进时间复杂度的规则 1. 时间复杂度函数式T (N)中只保留最⾼阶项去掉那些低阶项 2. 如果最⾼阶项存在且不是1 则去除这个项⽬的常数系数 3. T (N)中如果没有N 相关的项⽬只有常数项⽤常数1 取代所有加法常数。
相关案例
void func1(int N)
{int count 0;for(int k 0; k 2 * N; k){count;}int M 10;while (M--){count;}printf(%d\n, count);
}
基本语句count 关于问题规模n 总执⾏次数的数学表达式为:f(n) n × 2 10 保留最⾼阶项省略最⾼阶项的系数后的⼤O渐进表⽰法为O(n) 。
void func5(int n)
{int cnt 1;while (cnt n){cnt * 2;}
} // ⽤递归计算 N 的阶乘
long long fac(int N)
{if(N 0) return 1;return fac(N - 1) * N;
}
递归算法时间复杂度求解⽅式为单次递归时间×总的递归次数。 注意这⾥只是简易的估算⽅式。递归算法的时间复杂度严谨的计算⽅法是利⽤主定理(Master Theorem)来求得递归算法的时间复杂度。 但是我们往后学习更加深⼊会发现⼤多是情况下我们并不需要计算出准确⽆误的时间复杂度 只需要根据做题经验简单估算⼀下即可。所以这⾥为了不增加⼤家负担对于递归算法我们仅 需掌握这样简易的计算⽅式即可。 单次递归没有循环之类所以时间复杂度为常数。总的递归次数就是递归过程中 递归调⽤了多 少次。 F ac F ac(5) 需要递归6 次则F ac(n)就需要递归n 1 次故递归求阶乘的时间复杂度为O(n) 。
