本站最新发布   C#从入门到精通
试听地址  https://www.xin3721.com/eschool/CSharpxin3721/

Log–logplot. 绘制log图也是衡量运行时间的一种方法，因为是log级别的，所以与上面说的经验公式没有本质区别，如下图右所示，取完对数后，输入数据大小与运行时间的对数变为线性关系。

 

数学分析 总的运行时长受到两个主要指标影响：

• 执行每一个语句的成本

• 执行每一个语句的次数

 

其中，第一个是系统属性，后面一个是算法的属性。假如我们知道了程序中所有指令的这两个属性值，那么两者相乘求和后便是整个程序的运行时间。

主要的挑战是确定第二个指标，即语句的执行次数。一些语句是很容易分析出执行次数，比如将count 设置初始值为 0，在 ThreeSum.count()中仅仅执行一次。

但是，有些需要更高层次的推理演算才能得到语句的执行频次，比如 if 语句被执行的次数恰好为：n(n-1)(n-2)/6.

 

 

4波浪线符号

 

我们用波浪线符号形成更加简单的近似表示。首先，我们用数学表达式的主项作为波浪线的近似表示。写作：∼g(n) . 表示为算法的时间复杂度，当它被 f(n) 除的时候，随着 n 的增大，g(n) 接近1. 我们也可以写 g(n) ~ f(n) 表示，随着 n 的增大g(n)  / f(n) 接近1。

 

在这个表示下，我们忽略表达式中次要项。例如，在 ThreeSum.count()中的 if 语句的执行次数用波浪线表示为：∼n³/6. 因为 n(n-1)(n-2)/6 = n³/6 –n²/2+ n/3，当被n³/6 相除时，随着 n的增长，等于1.

 

我们专注于那些执行次数最多的指令，有时指内层循环。在 ThreeSum.java 程序中，我们可以合理地推理出内层循环以外的指令相对来说不重要。

 

 

5增长的阶数(order of growth)

 

分析一个程序的运行时长时，关键的一个点是大多数程序的运行时长满足关系：T(n) ~cf(n)，此处c是一个常数，f(n)是一个关于时间的增长阶次函数。对于一些典型的程序，f(n)是一个函数，例如： log₂n,  n, nlog₂n, n² , n³

 

再看ThreeSum.java程序，增长的阶数等于 n³ , 常数c的值取决于执行指令的成本和次数的细节上，但是我们通常不需要算出精确值。刚才说加倍输入数据个数，运行时长变为原来8倍，具体推导公式如下：

 

 

下面详细列出程序的增长阶数的典型例子：

 

 

 

6内存消耗

 

除了需要考虑时间成本，我们也要注意内存消耗。内存消耗在Java程序中很好地被定义，但是java程序可以编译在各种不同配置环境的计算设备上，内存消耗因实现方式不同而不同，在这里讨论java中三种类型的内存消耗。

 

原生类型(Primitive types) 例如，因为java int数据类型是整数值的集合，取值范围位于：−2,147,483,648 ~ 2,147,483,647，所占的字节数为4个。如下图所示为主要原生类型所占的内存字节数：

 

 

 

对象(objects) 为了确定一个对象的内存消耗，我们需要求以下两者的和：

• 每一个实例的内存消耗

• 每一个对象关联的头部消耗，典型的是8个字节

例如，一个复数对象消耗内存为32个字节，其中16个字节被头部所占，另外，每个double变量各占8个字节。

 

 

 

对一个对象的引用通常消耗8个字节的内存。当一个数据类型包含一个对象的引用时，我们必须单独分配8个字节用于存储引用关系，每个对象的头部消耗16个字节，还包括此对象的实例变量所耗内存。

 

 

数组和字符串(Arraysand strings) 在java中，数组是通过objects被实现的，典型的实现方法：带有2个实例变量，一个指针指向第一个元素的首地址，另一个指向元素长度。对于原生类型，含有 n个元素的数组用24字节的头部信息，另外包括存储一个元素需要的字节数乘以元素个数。典型的例子如下：