成都网站建设天府软件园,山东德州如何网站建设教程,开鲁企业网站建设,网站建设费 会计分录一、前篇
1、什么是数据结构#xff1f;
数据结构是带有结构特性的数据元素的集合#xff0c;它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系 2、时间复杂度与空间复杂度 大O符号是用于描述函数渐进行为的数学符号
常用函数的增长表 阶乘O(n!) 指数…一、前篇
1、什么是数据结构
数据结构是带有结构特性的数据元素的集合它研究的是数据的逻辑结构和数据的物理结构以及它们之间的相互关系 2、时间复杂度与空间复杂度 大O符号是用于描述函数渐进行为的数学符号
常用函数的增长表 阶乘O(n!) 指数阶(2^n) 立方阶O(n^3) 平方阶O(n^2) 线性对数阶O(nlog2n) 线性阶O(n) 对数阶O(log2n) 常数阶O(1)
从立方阶开始时间复杂度较大
二、二分查找
在有序数组中查找一个值如果找到了则返回下标如果没找到则返回-1
方法一遍历数组进行查找
时间复杂度O(n) //1.遍历算法在数组中查找一个元素
//方法体
int search(int* arr, int length, int target) {for (int i 0; i length; i) {if (arr[i] target) {return i;}}
}
方法二减小循环次数进行遍历查找
时间复杂度小于O(n)
因为题目里声明是有序数组所以当数组中的值比查找的值大时可以直接break跳出循环减少循环次数 //2.减小循环次数进行遍历查找
//方法体
int search2(int* arr, int length, int target) {for (int i 0; i length; i) {if (arr[i] target) {return i;}if (arr[i] target) {break;}}return -1;
}
方法三;二分查找
二分思想就是将一个 有序数组 不断进行平分直到找到为止不断平分除以二降低时间复杂度
时间复杂度O(og2n) //3.二分查找
//方法体
int binarySearch(int* arr, int target, int left, int right) {if (left right) {return -1;}int mid (left right) / 2;if (arr[mid] target) {return mid;}if (arr[mid] target) {mid binarySearch(arr, target, left, mid - 1);return mid;}else {mid binarySearch(arr, target, mid 1, right);return mid;}
}int search3(int* arr, int length, int target) {return binarySearch(arr, target, 0, length - 1);
}
