Java&C++运行速度测试

这周Java实验报告里有个要求是：每次在数组头插入一个数，操作100万次，计算用时。一时好奇就测一下Java一秒能执行多少次循环。

Java 代码：

惊了，一秒钟循环接近 2×10^8 次，这比我想象中快太多了… 后来换了Eclipse，测出来也差不多。于是我打算顺便把C++也测了。

C++代码：

一秒钟循环 1×10^8 还有点勉强，让我怀疑我自带隐形大常数。 换用VS的话就更惨不忍睹，一秒只能 1×10^7 ，谁让人家是大工程呢..

 

后来查了一下，Java为什么比C++慢。所以只是循环的话二者差距应该不是很大。 这样以上内容就用作时间复杂度估计了。一秒1e8

【算法笔记】稳定婚姻匹配问题-GS算法

最近在做算法复健，鉴于我的blog域名难产，暂时寄居在何dalao这里。

什么是稳定(婚姻)匹配问题

这里是百度百科。有N男N女，均为异性恋，每个人都对异性有好感度排序。如何将他们两两配对，才能尽可能使结果令每个人都满意。

当然也有N男M女、多对一的情况，这里先不讨论（网上有些大牛写了论文）。

处理方案

被广泛认可的算法是由美国数学家 David Gale 和 Lloyd Shapley 于1962年发明的 Gale-Shapley算法，简称GS算法。GS算法的思路如下：

先给N男N女从0~N-1分别编号，然后要求每个人写出他们对异性的好感度排序。为了方便，这里N取4.比如0号男最喜欢3号女，[……]

继续阅读

【算法笔记】二分查找

最近在做算法复健，鉴于我的blog域名难产，暂时寄居在何dalao这里。

什么是二分查找

二分查找又名折半查找。在一个有序数列中查找某个特定数/对象时，可以根据数的大小关系，每次将查找范围缩小到原来的一半，从而将查找所需的时间从O（n）缩小为O(logn).

举例：我需要在[1,4,5,7,12,15,19,27,33,41,49]这11个数中查找27.

如果正常按顺序检索，需要检索8次，当数据范围扩大到n时，时间复杂度为O(n).

如果采用二分查找，查找顺序如下：

  1. 记原数组为数组①，比较数组①中间的数（即15）与27的大小关系
  2. 由于15<27，检索数组修改为[19,27,33,[……]

    继续阅读

【算法笔记】时间复杂度和空间复杂度

最近在做算法复健，鉴于我的blog域名难产，暂时寄居在何dalao这里。

时间复杂度

时间复杂性，又称时间复杂度，它定性描述该算法的运行时间，这、是一个代表算法输入值的字符串的长度的函数。时间复杂度常用O表述，不包括这个函数的低阶项和首项系数。

上文摘自百度百科。

简单来说，时间复杂度是：程序每运行一次需要进行运算的次数。这里的“运算”一般指一个语句，也就是写代码时的一行代码。

当这个次数为较小的常数（计算机1秒大约能进行10^8次运算，如果远小于这个数，可以视为常数）时，一般表示为O(1)。 当这个次数中含有未知数（即，计算次数与输入的某个值有关）时，一般用n表示未知数，只保留次数最高的项，[……]

继续阅读