做电影网站程序好用吗,旅游商务网站建设,定西市网站建设企业,页面设计公司【1】 数学基础1.1#xff09;本书将使用以下4个定义#xff1a; 对上述定义的分析#xff08;Analysis#xff09;#xff1a; - A1#xff09;第一个定义是说T#xff08;N#xff09;的增长率小于等于f#xff08;N#xff09;的增长率#xff1b;- A2#x… 【1】 数学基础 1.1本书将使用以下4个定义 对上述定义的分析Analysis - A1第一个定义是说TN的增长率小于等于fN的增长率 - A2第二个定义是说TN的增长率大于等于gN的增长率 - A3第三个定义是说TN的增长率等于hN的增长率 - A4第四个定义是说TN的增长率小于pN的增长率 它不同于大O因为大O 包含增长率相同这种可能性 1.2我们引入了相对增长率的概念 并将其应用到算法分析 1.3比较1000N 与 N^2 的大小 虽然N 较小时1000N 大于 N^2 但 N^2 以更快的速度增长因为N^2 最终将更大 1.4这种情况下N1000 是个转折点 第一个定义说最后总会存在某个点 n0 从它以后 cf(N) 总是至少与 T(N)一样大 从而忽略掉常数因子 则f(N) 至少与 T(N) 一样大 1.5上界与下界 当我们说TNOfN时我们是在保证函数TN是在不快于fN的速度增长因此fN是TN的一个上界 也可以说fNΩTN意味着TN是fN的一个下界 1.6直观上说 1.7我们需要掌握的结论为 1.8以上信息足以按照增长率对大部分常见的函数进行分类如下图 【2】递归简论 1当编写递归例程的时候关键是要牢记递归的四条基本法则-PrincipleP1基准情形必须总是有某些基准情形它无需递归就能解除 P2不断推进对于那些需要递归求解的情形每一次递归调用都必须要是求解状况朝接近基准情形的方向前进 P3设计法则假设所有的递归调用都能运行 P4合成效益法则compound interest rule在求解一个问题的同一实例时 切勿在不同的递归调用中作重复性工作 Attention凡是可以用循环代替的 递归函数他就不是一个好的递归函数因为当一个递归可以被转化为循环时其递归使用效率低得离谱【3】递归荔枝荔枝1F(0)0 且 F(x)2F(x-1)x^2 #include stdio.h// compute the expr F(0)0 且 F(x)2F(x-1)x^2 int func(int x)
{if(x0){return 0;}return 2*func(x-1) x*x;
}int main()
{int x 1; for(;x10;x){printf(func(%d) %d \n, x, func(x));}
}荔枝2打印整数 1234 - 1 2 3 4 #include stdio.h// output the single integer towards given x.
// ex. 1234 should output as 1 2 3 4.
void printOutput(int x)
{if(x10){printOutput(x/10);}printf(%d , x%10);
}int main()
{int x[] {12345, 123456, 1234567, 12345678, 123456789};int length 5;int i 0;for(;ilength;i){printf(printOutput(%d) , x[i]);printOutput(x[i]);printf(\n);}
}
