本文主要是介绍北航计算机软件技术基础课程作业笔记【1】，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
为白成刚老师的课程，简单做一个记录，内容偏基础，自己仅保留认为有用的部分
L1：算法概论
课程简单介绍了复杂度、算法的概念
1.作业
计算下列各片断程序中x=x+1的执行次数
(1)
for (i=1; i<n; i++)for (j=1; i<n; j++)for (k=1; i<n; k++)x=x+1;内层的x=x+1位于三重循环中，但由于内两层判断条件均为最外层变量，且不对其进行修改，故
在n=0或1时，该代码执行0次（一般不会这样）；n>1时，该段代码片是无限循环
O（∞）
(2)
i=1；
while (i<n)
{x=x+1;i=i+1;
}一层循环，内层x=x+1需要执行n-1次才能退出，故
O(n)
(3)
for (i=1; i<n; i++)j=1;
for (k=j+1; k<n; k++)x=x+1;第一个for循环中，j被赋值1，在第二个循环中国，k的初值为2，那么x=x+1执行n-2次
O(n)
(4)
for (i=1; i<n; i++)
{ j=i; //执行n次while (j>=2){j=j/5; //执行log5(i)次x=x+1;}
}外层的for循环执行n次，但内层的执行次数取决于i的值，于是为如下式子，并化简
分析时间复杂度，即为
O(log5n!)
或者放大上界至线性对数
O(n*log5n)
(5)
k=100000;
while (k!=5)
{k=k/10;x=x+1;
}该循环的条件无法达到，故该循环也无法终止，语句的运行次数为无穷大。
O（∞）
（作业中有用的知识点记录）
2.复杂度分析
（1）复杂度表示
时间复杂度表示方式：O（g(n)）
定义以下式子：
含义为：
用于描述最坏复杂度
一般常数<对数<线性<线性对数<幂次<指数
（2）分析方法——渐进分析法
选择算法内重复执行次数最多的基本语句，作为算法执行时间量度。一般情况下是最深层循环内的基本语句。
这篇关于北航计算机软件技术基础课程作业笔记【1】的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
