五个特征
有穷性、确定性、可行性、有输入、有输出
两个重要指标
- 时间复杂度：运行一个程序所花费的时间，常用大O表示法反映时间复杂度，计算时间复杂度往往是计算比较大的，是不确定的数，如果已经确定了，那么就不用计算了，也是我们说的常量，常见如下表示方法：
常数：O(1), 1表示确定的步骤，是常数
对数：O(logn) ,
线性：O(n)，算法复杂度与不定参数n有关，随着n增大，复杂度线性增长。
线性对数：O(n logn), 平方：O(n^2)
N次方：O(n^n) - 空间复杂度：运行程序所需要的内存OOM
减少时间与空间复杂度是算法迫切要解决的问题
设计原则
正确性、可读性、健壮性，少bug，系统健壮性比较稳定。
思考题
1.从一堆数据中快速找到是2的N次方的数字
解法：2的N次方转换成二进制有如下特点：
2 => 10
(2-1) => 01
4 => 100
(4-1) => 011
8 => 1000
(8-1) => 0111
......
得出结论：( 2^n & (2^n -1)) == 0
代码如下：
private static boolean check(long num) {
if (num < 1) {
return false;
}
if ((num & (num - 1)) == 0) {
return true;
}
return false;
}
2.给定一个文件，包含全国所有14亿人员的年龄，要求快速统计每个年龄对应的人数量
假定文件是age.txt，文件大小大约在5GB左右，给的计算机是2G内存 + 2核CPU，磁盘空间够存放文件，不允许使用java中现有的数据结构。
文件中每行存储了一个年龄数字，如下：
12
34
9
50
......
解法：定义一个长度200的数组，数组下标0-199，每个下标表示年龄，每个下标对应的值初始为0，解析文件每行数据，并将年龄对应的下标的值加1，这样便能快速统计出所有年龄的人员数量
代码如下：
生成age.txt代码
BufferedWriter out = null;
try {
int total = 1400000000;
Random random = new Random();
out = new BufferedWriter(new FileWriter("/temp/age.txt"));
for (int i = 0; i < total; i++) {
int age = random.nextInt(130);
out.write(String.valueOf(age));
out.newLine();
}
System.out.println("文件创建成功！");
} catch (IOException e) {
e.printStackTrace();
} finally {
try {
out.close();
} catch (IOException e) {
e.printStackTrace();
}
}
求年龄对应的数量的代码：
try {
// 数据文件地址
String fileName = "/temp/age.txt";
// 存储年龄数量的数组
int data[] = new int[200];
// 文件中年龄数据的总行数
int tot = 0;
long start = System.currentTimeMillis();
InputStreamReader isr = new InputStreamReader(new FileInputStream(fileName), "UTF-8");
BufferedReader br = new BufferedReader(isr);
// 时间复杂度 O(n)
String str = "";
while ((str = br.readLine()) != null) {
int age = Integer.valueOf(str);
// 年龄做为数组下标，将下标对应的数组值自增1
data[age]++;
// 总数量自增1
tot++;
}
System.out.println("总共的人数：" + tot);
for (int i = 0; i < 200; i++) {
System.out.println(i + ":" + data[i]);
}
System.out.println("计算花费的时间为：" + (System.currentTimeMillis() - start) + "ms");
} catch (Exception e) {
e.printStackTrace();
}
常见算法复杂度分析参考
// 1次 O(1)
int a = 1;
// 3次，是常数阶 算法复杂度是O(1)
for (int i = 0; i < 3; i++) { // 这里运行4次，在第四次结束
a = a + 1; // 这里运行3次
}
int n = Integer.MAX_VALUE; // 表示n是未知的
int i = 1;
// 算法复杂度 O(logn)
while (i <= n) {
i = i * 2;
}
// i的值：2,4,8,16...... 2^n,计算次数 x = log2n 计算机里面要忽略常数即：O(logn)
// 算法复杂度 O(nlogn)
for (int j = 0; j < n; j++) {
while (i <= n) {
i = i * 3;
}
}
// 运行n次 算法复杂度 O(n)，
// 如果n是已知的，则是O(1)；
for (i = 0; i < n; i++) {
a = a + 1;
}
// 外层运行n次，固定的，内层运行次数如下：
// i = n :1次
// i = n - 1 :2次
// ...
// i = 1运行n次
// 总共：n*(n+1)/2 约等于 n^2 => 算法复杂度O(n^2)
// 注意有个规律，有加减法的时候，找次数最高的那个
// 例如冒泡排序时间复杂度就是这样的
for (i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
a = a + 1;
}
}
下一节：算法与数据结构-数组/链表
