其实,以前我们都会说,学习数据结构有多么多么的重要,长篇大论。这次,我们java程序员来看看数据结构和算法重要性。
拿到这道题,用java的思路分析:
2:2
4:2*2
8:2 * 2 * 2
16:2 * 2 * 2 * 2
如果一个数除以2,最后余数是0,那么这个数就是2的n次方;如果余数是1,那么就不是。代码实现如下:
public static void main(String[] args) {
// 随意给一个数,判断这个数是不是2的n次方
int n = 16;
int yuShu = n%2;
int chuShu = n/2;
while (chuShu > 1) {
yuShu = chuShu % 2;
chuShu = chuShu / 2;
}
System.out.println( n + " 这个数" + (yuShu == 0?"是":"不是")+"2的n次方");
}
但是,如果使用数据结构呢?下面来分析一下:将所有的十进制数字都转成2进制
2:10
4:100
8:1000
16:10000
他们的特点是什么呢?第一个数字是1,其余的都是0
而这几个数字之前的一个数字是什么呢?
1:01
3:011
7:0111
15:01111
他们的特点是什么呢?第一个是0,其余的都是1.
利用这两组数字,我们找规律,如果i和i-1按位&与的结果是0,就说明这个i是2的n次方;否则就不是
2 & 1 = 0
4 & 3 = 0
8 & 7 = 0
16 & 15 = 0
但是15 & 14呢,14的二进制数是01110,01111 & 01110 = 00001
所以,通过对数据的分析,我们可以用一句代码判断
if(n & (n=1) == 0) {
// 这个数就是2的n次方
} else {
// 否则不是
}
数据结构包括:线性结构和非线性结构
1)线性结构是最常用的数据结构,其特点是数据元素之间存在一对一的线性关系。
2)线性结构有两种不同的存储结构,即顺序存储结构和链式存储结构。顺序存储的线性表成为顺序表,顺序表中的存储元素是连续的
3)链式存储的线性表成为链表,链表中的存储元素不一定是连续的,元素节点中存放数据元素以及相邻元素的地址信息。
4)线性结构常见的有:数组、队列、链表和栈,后面我们会详细讲解
非线性结构包括:二维数组、多维数组、广义表、树结构、图结构
算法有五个特征:有穷性,确定性,可行性,有输入,有输出
正确性,可读性,健壮性,bug(写出的代码bug少,而且系统稳定)
高效率与低存储:内存+CPU 堆栈内存 OOM
内存占用最小,CPU占用最小,运算速度最快。
评价算法的两个重要指标:时间复杂度 和 空间复杂度
时间复杂度:运行一个程序所花费的时间。
空间复杂度:运行程序所需要的内存。
计算时间复杂度,通常是计算比较大的,而且是不确定的的数。如果是已经确定的,那么就不用计算了,常量就是我们说的不用计算的一种。
比如下面的这个循环,时间复杂度是O(1)
public class BigO {
public static void main(String[] args) {
int n = 0; // 这句话的时间复杂度是O(1)
for (int i = 0; i < 3; i++) { // 这句话会执行4次, 它的时间复杂度也是O(1)
n = n + 1; // 这句话会执行3次, 他的时间复杂度也是O(1)
}
}
}
那么什么情况下会使用时间复杂度是对数的这种情况呢?来看一下下面的代码:
public static void time_log() {
int a = Integer.MAX_VALUE;
int i = 1;
while (i <= a) {
i = i * 2; // 这个循环一共要循环多少次呢?
// 我们来看看i的值2,4,8,16,32,64,128 2^0,2^1,2^2,2^3,2^4,2^5 ====> 2(n) = a ===> n = log2a
}
}
这里i = i * 2 这句话需要循环多少次呢?其实我们要求的就是:循环多少次,i<= a 呢?2^n = a ; 求n=log2a, log以2为底a的对数。
以上是O(logn)的情况,那么什么情况下使用O(nlogn)呢?看下面的代码:
public static void time_nlogn() {
int a = Integer.MAX_VALUE;
int i = 1;
for (int j = 0; j < 10; j++) {
while (i <= a) {
i = i * 2; // 这个循环一共要循环多少次呢?
// 我们来看看i的值2,4,8,16,32,64,128 2(1),2(2),2(3),2(4),2(5) 2(n) = a ===> n = log2a
// 外面还有个j,所以就是(j * log2a)次
}
}
}
只有while循环的时候,需要执行log2a次。那么外面多了一层for循环,这次要循环多少次呢?(j * log2a)次
线性指的就是O(n),也就是运行n次。
public static void time_on() {
int n = Integer.MAX_VALUE;
int a = 0;
for (int i = 0; i < n; i++) {
a = a + 1; // 这句话的时间复杂度是什么? O(n) n是几就运行几次. n是未知的,不确定的.如果n是确定的,就是常量了. 时间复杂度就是O(1)
}
}
这里面a = a + 1;这句话会运行多少次呢?他和n有关系,如果n是10就运行10次,n是100就运行100次。有n决定,所以时间复杂度是O(n);
注意:这里的n是不确定的。如果n是确定的,那么时间复杂度就是O(1)le
这个在上面已经说过了
/**
* 时间复杂度O(n^2)
*/
public static void time_Onn() {
int n = Integer.MAX_VALUE;
int a = 0;
for(int i = 0; i < n; i++) {
for (int j = 0; j< n; j++) {
a = a + 1; // 这句话执行多少次呢?也就是说它的时间复杂度是多少呢? 外层循环执行n次,内层循环也是n次,所以最终执行n*n次,所以时间复杂度是O(n^2)
}
}
}
这里有两层循环,外层循环执行n次,内存循环也是n次,所以代码a = a + 1;执行O(n*n)次。
常见的O(n^2)还有冒泡排序
public static void time_Onn2() {
int[] num = {3,6,1,0,8,5};
int n = num.length;
int a = 0;
for(int i = 0; i < n; i++) {
for (int j = i; j < n; j++) {
a = a + 1; // 这句话执行多少次呢?也就是说它的时间复杂度是多少呢? 来找找它的规律
/*
* 外层循环i=n, 内层代码执行1次
* 外层循环i=n-1,内层代码执行2次
* 外层循环i=n-2,内层代码执行3次
* 外层循环i=n-3,内层代码执行4次
* 外层循环i=1,内层代码执行n次
*
* 一共执行多少次呢? 0+1+2+3+......+n = n * (n+1)/2次
* 也就是冒泡算法的时间复杂度是O(n*(n+1)/2)次
*/
}
}
}
冒泡排序的时间复杂度是多少呢?我们来分析一下:
外层循环i=n, 内层代码执行1次 外层循环i=n-1,内层代码执行2次 外层循环i=n-2,内层代码执行3次 外层循环i=n-3,内层代码执行4次 外层循环i=1,内层代码执行n次
一共执行多少次呢? 0+1+2+3+......+n = n * (n+1)/2次 也就是冒泡算法的时间复杂度是O(n*(n+1)/2)次。
在计算时间复杂度的时候去掉常数,所以就是O(n^2)
如果是三层循环,四层循环呢?那就是 n * n * n * n=n^4
上面的冒泡算法会执行n*(n+1)/2 = (n^2 + n)/2 ===>当有加减法的时候,这个时间复杂度怎么计算呢? 取最大的就可以,这个最大是:首先去掉常数后,n2比n的阶层高,所以最后是O(n2)
网络请求可以通过打印日志来计算时间。
O(1) > O(logn) > O(n) > O(nlogn) > O(n^2) > O(n^x) O(1)的运行效率是最高的。 所以,我们在优化的时候,目标是将所有的时间复杂度往O(1)进行优化。 实际上,O(1) > O(logn) > O(n) > O(nlogn) 效果都是很好的,几乎优化的空间不是很大。我们的最终目标就是将O(n^2) 和 O(n^x)往前优化。
再来看看最开始的这个案例:判断一个数是否是2的n次方。比如:2,4,8,16是2的n次方;6,10不是。
如果一个数除以2,最后余数是0,那么这个数就是2的n次方;如果余数是1,那么就不是。代码实现如下:
public static void main(String[] args) {
// 随意给一个数,判断这个数是不是2的n次方
int n = 16;
int yuShu = n%2;
int chuShu = n/2;
while (chuShu > 1) {
yuShu = chuShu % 2;
chuShu = chuShu / 2;
}
System.out.println( n + " 这个数" + (yuShu == 0?"是":"不是")+"2的n次方");
}
那么这段代码的时间复杂度是多少呢?log2n:log以2位底n的对数。O(logn)
后来通过二进制代码进行优化,优化后的结果是
if(n & (n=1) == 0) {
// 这个数就是2的n次方
} else {
// 否则不是
}
这段代码的时间复杂度是O(1)。
我们优化以后,将O(logn)优化为O(1)了,效率大大提高了
比如,我们在看一段代码的时候,发现有性能瓶颈,然后这段代码使用的排序方式是冒泡排序,如何对这个排序进行优化呢?
找更优秀的替代排序方法,快速排序,归并排序,堆排序等。
找出哪些地方花费内存多,哪些数据占用的内存开销大
开空间的地方,比如:数组,链表,缓存Map,Set,队列Queue,递归等
数据结构和算法书籍推荐