浦项建设(中国)有限公司网站,正品购物平台,苏州网站制作公司,网站建设 文章什么是数据结构
数据结构是由#xff1a;“数据”与“结构”两部分组成
数据与结构 数据#xff1a;如我们所看见的广告、图片、视频等#xff0c;常见的数值#xff0c;教务系统里的#xff08;姓名、性别、学号、学历等等#xff09;#xff1b; 结构#xff1a;当…什么是数据结构
数据结构是由“数据”与“结构”两部分组成
数据与结构 数据如我们所看见的广告、图片、视频等常见的数值教务系统里的姓名、性别、学号、学历等等 结构当我们面对海量的数据时我们时常无法下手寻找数据是不方便的可读性就很差而结构则是将这些数据以各种不同的形式进行排序使我们便于寻找 数据结构是计算机存储、组织数据的方式。是数据之间存在一种或多种相互关系的集合 什么是算法
算法(Algorithm)就是定义良好的计算过程他取出一个或一组数据为输入产出一个或一组的值为输出。简单来说算法就是一系列的计算步骤用来将输入数据转化成输出结果。
算法一般分为排序递归与分治回溯DP贪心搜索算法、二分查找、水桶法等等
算法往往数学密切相关就如数学题一样每道数学题都有不同的解法算法也是同理
复杂度分析
我们如何评判算法的效率呢问题的解决方法有很多对于计算机而言我们需要找到问题的最优解为了寻找到这个最优解我们需要从两个维度评判
时间效率算法运行的快慢空间效率算法所占空间的大小
评估方法实验分析与理论分析
对于实验分析而言
相同的算法在不同的电脑它们所运行的时间也许会有很大的出入当面对大量的数据而言同一台电脑时间上的差距则会变为很大导致误差的增大有些算法在少量数据时运算速度不快在大量数据中反之
由于实验分析法的局限性就有人提出了一种理论测评的方法就是渐近复杂度分析(asymptotic complexity analysis)简称复杂度分析。
这种方法体现算法运行所需的时间空间资源与输入数据大小之间的关系能有效的反应算法的优劣。
时间复杂度与空间复杂度
时间复杂度
指一个算法所花费的时间与其中语句的执行次数成正比例算法中的基本操作的执行次数为算法的时间复杂度。让我们计算下方代码的时间复杂度
int main()
{int n10;//对于时间复杂度而言当数据为n时下方代码区运行次数10时间复杂度为O(n)while (n--) {printf(%d, n);}//在时间复杂度中我们会忽略除最高次的所有项//忽略所有系数return 0;
}
实际上我们不可能对执行次数的统计精确并且为理论分析当n-∞时最高次的影响会远远超过非最高次的项所以O(n)的数量级由最高次决定所以当我们计算时间复杂度时可以简化为以下两个步骤
忽略除最高次的所有项忽略所有系数
思考
当我们遍历下方数组查找2时我们需要4次 当长度为n的数组中存放的是无序自然数时他们是没有规则的此时我们查找2的次数[ 1 , n ] 此时我们需要将最坏的情况作为时间复杂度 空间复杂度
空间复杂度也是一个数学表达式是对一个算法在运行过程中临时占用存储空间大小的量度 。空间复杂度的表示也遵循大O的渐进表示法
让我们计算一下冒泡排序的空间复杂度
// 计算BubbleSort的空间复杂度
void BubbleSort(int* a, int n)
{assert(a);for (size_t end n; end 0; --end){int exchange 0;for (size_t i 1; i end; i){if (a[i - 1] a[i]){Swap(a[i - 1], a[i]);exchange 1;}}if (exchange 0)break;}
}//在冒泡排序中我们只开辟了一块空间所以空间复杂度为O(1);
复杂度的分类
算法的复杂度有几个量级表示如下 O(1)O(logN)O(N)O(NlogN)O(N2)O(2N)O(N!) 如图下列 常数阶O(1)
int main()
{int n 4;while (n--) {printf(%d, n);//执行次数为常数}return 0;
}
对数阶O(logn)
int binary_search(int nums[], int size, int target)
//nums是数组size是数组的大小target是需要查找的值
{ int left 0;int right size - 1; // 定义了target在左闭右闭的区间内[left, right]while (left right) { //当left right时区间[left, right]仍然有效int middle left ((right - left)1);//等同于 (left right) / 2防止溢出if (nums[middle] target) {right middle - 1; //target在左区间所以[left, middle - 1]} else if (nums[middle] target) {left middle 1; //target在右区间所以[middle 1, right]} else { //既不在左边也不在右边那就是找到答案了return middle;}}//没有找到目标值return -1;
}线性阶O(n)
int main()
{int n;scanf(%d, n);int court 0;for (int i 0; i n; i) {court i;//计算和}return 0;
}
以下为空间复杂度为O(n)
int main()
{int n;scanf(%d, n);int* p (int*)malloc(sizeof(int) * n);//开辟大小为n的空间if (p NULL){perror(malloc fail);return -1;}free(p);p NULL;}
线性对数阶O(nlogn)
无论是时间复杂度还是空间复杂度线性对数阶都是在循环嵌套里实现即为一层为O(n),另一层为O(logn);
所以我们可以利用二分查找打印
int binary_search(int nums[], int size, int target) //nums是数组size是数组的大小target是需要查找的值
{int left 0;int right size - 1; // 定义了target在左闭右闭的区间内[left, right]while (left right) { //当left right时区间[left, right]仍然有效int middle left ((right - left) / 2);//等同于 (left right) / 2防止溢出if (nums[middle] target) {right middle - 1; //target在左区间所以[left, middle - 1]}else if (nums[middle] target) {left middle 1; //target在右区间所以[middle 1, right]}else { //既不在左边也不在右边那就是找到答案了printf(%d , nums[middle]);}}//没有找到目标值return -1;
}void func(int nums[], int size, int target)
{for (int i 0; i size; i){binary_search(nums, size, target);}
}
平方阶O(n)
莫过于我们最为熟悉的冒泡排序
void BubbleSort(int* a, int n)
{assert(a);for (size_t end n; end 0; --end){int exchange 0;for (size_t i 1; i end; i){if (a[i - 1] a[i]){Swap(a[i - 1], a[i]);exchange 1;}}if (exchange 0)break;}
}
指数阶O(2^n)
指数阶的算法效率低下并不常见
最为常见的指数阶为递归实现斐波那契数列
int Fib1(int n)
{if (n 1 || n 2){return 1;}else{return Fib1(n - 1) Fib1(n - 2);}
}
