一.为什么要学习数据结构和算法
1.大公司面试必备
- Oracle,SQLserver,MySQl,SQlite等数据库底层都会用到数据结构和算法:B树 哈希表
区块链,比特币 :链表,二叉树,哈希函数
人工智能AR VR 无人驾驶 都会用到
3.写出性能更高的程序,快速学习新技术
学好数据结构和算法和编程语言无关,只要学好了思想,他们都是相通的
二.如何评判一个算法的好坏
OC 代码实现斐波那契数列
- (void)viewDidLoad {
[super viewDidLoad];
// Do any additional setup after loading the view.
// 斐波那契数列
// 0 1 1 2 3 5 8 13 ...
NSLog(@"%d",[self fib:0]);
NSLog(@"%d",[self fib:1]);
NSLog(@"%d",[self fib:2]);
NSLog(@"%d",[self fib:3]);
NSLog(@"%d",[self fib:4]);
// 数字很大就会很耗时
NSLog(@"%d",[self fib:42]);
// //
// NSLog(@"%d",[self fib2:42]);
}
// 递归方式
- (int)fib:(int)n {
if ( n<= 1) {
return n;
}
return [self fib:n-1] + [self fib:n-2];
}
//(性能好)
- (int)fib2:(int)n {
if ( n<= 1) {
return n;
}
int first = 0;
int second = 1;
for (int i = 0; i < n - 1; i ++) {
int sum = first + second;// 计算出来的sum实际上是下一次的second
first = second;// 下一次的计算first变成了second
second = sum;// 将第一步的sum赋值给second
}
return second;
}
//省略局部变量写法
- (int)fib3:(int)n {
if ( n<= 1) {
return n;
}
int first = 0;
int second = 1;
// 省略局部变量
while (n -- > 1) {
second = first + second;
first = second - first;
}
return second;
}
// 计算1+2=3+....+n的和 for循环
- (int)sum:(int)n {
int sum = 0;
for (int i = 0; i <= n ; i ++) {
sum += i;
}
return sum;
}
// 计算1+2=3+....+n的和 使用公式(性能好)
- (int)sum1:(int)n {
return (n + 1) * n / 2;
}
事后统计法:
如果单从执行效率上进行评估:可以比较不同算法对同一组输入的执行处理时间
缺点:执行时间严重依赖于硬件(不同CPU)以及运行时各种不确定的环境因素
测试数据的选择比较难保证公正性
一般会从几个维度来评估算法的优劣
1.正确性,可读性,健壮性(对不合理的输入的反应能力)
2.时间复杂度(time complexity):估算程序指令的执行次数(执行时间)
3.空间复杂度(space complexity):估算所需占用存储空间(需要用多少变量,开辟多少存储空间)
大O表示法(java举例)
public static void test1(int n) {
// 汇编指令
// 1
if (n > 10) {
System.out.println("n > 10");
} else if (n > 5) { // 2
System.out.println("n > 5");
} else {
System.out.println("n <= 5");
}
// 1 + 4 + 4 + 4
for (int i = 0; i < 4; i++) {
System.out.println("test");
}
// 140000
// O(1)
// O(1)
}
public static void test2(int n) {
// O(n)
// 1 + 3n
for (int i = 0; i < n; i++) {
System.out.println("test");
}
}
public static void test3(int n) {
// 1 + 2n + n * (1 + 3n)
// 1 + 2n + n + 3n^2
// 3n^2 + 3n + 1
// O(n^2)
// O(n)
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
System.out.println("test");
}
}
}
public static void test4(int n) {
// 1 + 2n + n * (1 + 45)
// 1 + 2n + 46n
// 48n + 1
// O(n)
for (int i = 0; i < n; i++) {
for (int j = 0; j < 15; j++) {
System.out.println("test");
}
}
}
public static void test5(int n) {
// 8 = 2^3
// 16 = 2^4
// 3 = log2(8)
// 4 = log2(16)
// 执行次数 = log2(n)
// O(logn)
while ((n = n / 2) > 0) {
System.out.println("test");
}
}
public static void test6(int n) {
// log5(n)
// O(logn)
while ((n = n / 5) > 0) {
System.out.println("test");
}
}
public static void test7(int n) {
// 1 + 2*log2(n) + log2(n) * (1 + 3n)
// 1 + 3*log2(n) + 2 * nlog2(n)
// O(nlogn)
for (int i = 1; i < n; i = i * 2) {
// 1 + 3n
for (int j = 0; j < n; j++) {
System.out.println("test");
}
}
}
public static void test10(int n) {
// O(n)
int a = 10;
int b = 20;
int c = a + b;
int[] array = new int[n];
for (int i = 0; i < array.length; i++) {
System.out.println(array[i] + c);
}
}
一般用大O表示法来描述复杂度,它表示的是数据规模n对应的复杂度
忽略常数,系数,低阶
数据规模小的时候
数据规模大的时候
分析递归fib的时间复杂度
1+2 +4 + 8 =
O(n)和O(2^n)
算法优化的方向
用尽量少的的存储空间
用尽量少的执行步骤(执行时间)
根据情况,可以空间换时间,时间换空间
更多内容:
最好、最坏复杂度
均摊复杂度
复杂度震荡
平均复杂度 等等
◼ 一个用于练习算法的好网站 https://leetcode.com/
https://leetcode-cn.com/
◼ 斐波那契数 https://leetcode-cn.com/problems/fibonacci-number/
什么是数据结构
1.线性表
线性表是具有n个相同类型元素的有限序列(n>=0)
每一个都有索引
常见的线性表有:数组,链表,栈,队列,哈希表(散列表)
数组
动态数组接口设计,至少包含以下借口
设计思路:
ArrayList 1.size属性元素的数量 2.elements数组所有元素
构造方法:创建指定容量的elements
/**
* 元素的数量
*/
private int size;
/**
* 所有的元素
*/
private E[] elements;
private static final int DEFAULT_CAPACITY = 10;
private static final int ELEMENT_NOT_FOUND = -1;
public ArrayList(int capaticy) {
capaticy = (capaticy < DEFAULT_CAPACITY) ? DEFAULT_CAPACITY : capaticy;
elements = (E[]) new Object[capaticy];
}
public ArrayList() {
this(DEFAULT_CAPACITY);
}
注意(如果是Int数据)这里clear操作,是不必把整个数据清掉的. (只需要size = 0)就可以
销毁内存和重新申请空间是要浪费时间和性能的
对于动态数组,add操作的规律
/**
* 在index位置插入一个元素
* @param index
* @param element
*/
public void add(int index, E element) {
rangeCheckForAdd(index);
ensureCapacity(size + 1);//后面实现,当容量不够时进行扩容
for (int i = size; i > index; i--) {
elements[i] = elements[i - 1];
}
elements[index] = element;
size++;
}
删除元素(数组内存是连续的,所以不能直接挖掉内存)
范围是index + 1 到 size-1
删除
添加元素(注意是从后面往前挪)
范围是index 到 size-1
抽取rangeCheck方法,来检测传入的index是否合法(注意add要单独写出来)
private void outOfBounds(int index) {
throw new IndexOutOfBoundsException("Index:" + index + ", Size:" + size);
}
private void rangeCheck(int index) {
if (index < 0 || index >= size) {
outOfBounds(index);
}
}
private void rangeCheckForAdd(int index) {
if (index < 0 || index > size) {
outOfBounds(index);
}
}
如何扩容
创建一份新的内存,再把原来的数据复制过来
/**
* 保证要有capacity的容量
* @param capacity
*/
private void ensureCapacity(int capacity) {
int oldCapacity = elements.length;
if (oldCapacity >= capacity) return;
// 新容量为旧容量的1.5倍
int newCapacity = oldCapacity + (oldCapacity >> 1);
E[] newElements = (E[]) new Object[newCapacity];
for (int i = 0; i < size; i++) {
newElements[i] = elements[i];
}
elements = newElements;
System.out.println(oldCapacity + "扩容为" + newCapacity);
}
改为泛型E
对象数组的存储
所以在实现clear的时候elements[i] = null,要释放掉对象,保留地址的内存,而不是elements= null
内存管理细节
内存管理细节
网友评论