陕西省住房和城乡建设厅门户网站,网站免费制作教程,网站demo制作工具,如何后台修改网站联系人目录 前言 1.什么是数据结构 2.什么是算法 3.数据结构和算法的重要性 1.算法的时间复杂度和空间复杂度 1.1算法效率 1.1.1如何衡量一个算法的好坏 1.1.2算法的复杂度 1.2时间复杂度 1.2.1时间复杂度的概念 1.2.2大O的渐进表示法 2.编程练习 2.1.1 排序遍历 2.1.2 2.1.3 单身狗解… 目录 前言 1.什么是数据结构 2.什么是算法 3.数据结构和算法的重要性 1.算法的时间复杂度和空间复杂度 1.1算法效率 1.1.1如何衡量一个算法的好坏 1.1.2算法的复杂度 1.2时间复杂度 1.2.1时间复杂度的概念 1.2.2大O的渐进表示法 2.编程练习 2.1.1 排序遍历 2.1.2 2.1.3 单身狗解法 1.3空间复杂度 前言
1.什么是数据结构
数据结构(Data Structure)是计算机存储、组织数据的方式指相互之间存在一种或多种特定关系的数据元素的集合。
2.什么是算法
算法(Algorithm):就是定义良好的计算过程他取一个或一组的值为输入并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤用来将输入数据转化成输出结果。
3.数据结构和算法的重要性
目前校招的笔试都是20-30左右的选择题2-4道的编程题算法题居多并且某些大厂的笔试题基本上都是算法编程题。 1.算法的时间复杂度和空间复杂度
1.1算法效率
1.1.1如何衡量一个算法的好坏
下面举一个使用递归思想 来实现斐波那契数列的例子
#includestdio.h
long long Fib(int N)
{
if(N3)
return 1;
else
return
Fib(N-1)Fib(N-2);
}
代码非常的简单但是会发现计算的数字再大一些时编译器会计算的特别慢
1.1.2算法的复杂度 算法在编写成可执行程序后运行时需要耗费时间资源和空间(内存)资源。因此衡量一个算法的好坏一般是从时间和空间两个维度来衡量的即时间复杂度和空间复杂度。时间复杂度主要衡量一个算法的运行快慢而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展计管机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。 1.2时间复杂度
1.2.1时间复杂度的概念
什么是时间复杂度运行一个程序所需要的时间吗显然不是的因为在不同的局域网中不同的机器上程序运行的速度也会有所差异于是有了以下时间复杂度的定义 时间复杂度的定义:在计算机科学中算法的时间复杂度是一个函数它定量描述了该算法的运行时间。一个算法执行所耗费的时间从理论上说是不能算出来的只有你把你的程序放在机器上跑起来才能知道。但是我们需要每个算法都上机测试吗? 是可以都上机测试但是这很麻烦所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例算法中的基本操作的执行次数为算法的时间复杂度 eg1
void Func1(int N)
{int count 0;for (int i 0; i N; i){for (int j 0; j N; j){count;}}for (int k 0; k 2 * N; k){count;}int M 10;while (M--){count;}printf(%d\n, count);
} 观察代码我们得出循环次数F(N)N^22*N10 即为时间复杂度的函数式。
该程序时间复杂度为O(N^2) 实际中我们计算时间复杂度时我们其实并不一定要计算精确的执行次数而只需要大概执行次数那么这里我们使用大O的渐进表示法。最大的量级取决定性结果那一项 N10 F(N)130; N100 F(N)10210; N100 F(N)1002010; 当N趋于正无穷时2*N对F(N)的影响远小于N^2 eg2:
void Func2(int N)
{int count 0;for (int k 0; k 2 * N; k){count;}int M 10;while (M--){count;}printf(%d\n, count);
}F(N)2*N10,时间复杂度为O(N), 取最高阶的项再去掉系数就是时间复杂度
eg3
void Func3(int N, int M)
{int count 0;for (int k 0; k N; k){count;}for (int k 0; k N;k){count;}printf(%d\n, count);
} 此时时间复杂度为O(MN)因为我们无法区分M和N 哪一个对程序影响较大 若M远大于N则时间复杂度为O(M) 若N远大于M则时间复杂度为O(N) 若NM则时间复杂度为O(M) OR O(N) eg4:
void Func4(int N)
{int count 0;for (int k 0; k 100000000; k){count;}printf(%d\n, count N);
}
int main()
{Func4(1);return 0;
}
看似循环的次数很多但是时间复杂度为O(1),1000000000看起来似乎很大但在无穷大的N面前就算是一个很小的数字所以单循环常数次的时间复杂度是O(1)
eg5
const char* strchr(const* str, int character);
//在str字符数组中查找一个字符
时间复杂度为 O(N)但是这个查找也有可能一次就查找到呀那为什么时间复杂度还是O(N)呢 通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项简洁明了的表示出了执行次数。另外有些算法的时间复杂度存在最好、平均和最坏情况: 最坏情况: 任意输入规模的最大运行次数(上界) 平均情况: 任意输入规模的期望运行次数 最好情况: 任意输入规模的最小运行次数(下界) 例如: 在一个长度为N数组中搜索一个数据x 最好情况: 1次找到 最坏情况: N次找到 平均情况: N/2次找到 在实际中一般情况关注的是算法的最坏运行情况所以数组中搜索数据时间复杂度为O(N) 时间复杂度计算时是一个稳健保守预期已经做了最坏的打算
1.2.2大O的渐进表示法 大O符号 (Big o notation) : 是用于描述函数渐进行为的数学符号.推导大阶方法: 1、用常数1取代运行时间中的所有加法常数 2、在修改后的运行次数函数中只保留最高阶项。 3、如果最高阶项存在且不是1则去除与这个项目相乘的常数。得到的结果就是大O阶. eg6计算冒泡排序的时间复杂度
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;}
}
观察冒泡排序的时间复杂度直接从代码中来看有点费力直接对代码内容进行分析将第一个数字排好需要n-1次第二个需要n-2次第三个需要n-3次以此类推需要的算次数是一个等差数列等差数列的和为N-1*N/2根据大O渐进式可知时间复杂度为O(N^2)
冒泡排序最小的时间复杂度为O(N)(排序时就已经有序了)
eg7二分查找法
int BiarySearch(int* a, int n, int x)
{assert(a);int begin 0;int end n - 1;while (begin end){int mid begin ((end - begin) 1);if (a[mid] x)begin mid 1;else if (a[mid] x)end mid - 1;else return mid;}return -1;
} 最坏的结果除以n次2之后才找到或者没有找到 2^xN xlogN; 二分法时间复杂度为logN本应是log以2为底的N但是符号难以表示故简写为logN 2.编程练习
数组 nums 包含从 0到 n的所有整数但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗?
这道题我们有三种办法来解决
2.1.1 排序遍历
若下一个数字不等于这个数字1则下一个数字为消失的数字
时间复杂度:O(logN*N)复杂度太高。
2.1.2
0-n为一个等差数列将0-n的和加起来再减去数组中数值的和得到的结果就是消失的数字
时间复杂度为O(N);方法1和2比较很明显2要简单。下面对2进行实现
int missingNumber(int* nums, int numsSize)
{int N numsSize;int ret N*(N - 1) / 2;for (int i 0; i N; i){ret - nums[i];}return ret;
}2.1.3 单身狗解法
这个解法需要用到^异或按位异或相异为1相同为0
两个相同的数字异或的结果为0
2^3^2^3结果还是0满足交换律
下面代码进行实现
int missingNumber(int* nums, int numsSize)
{int N numsSize;int x 0;for (int i 0; i N; i){x ^ i;}for (int i 0; i N; i){x ^ nums[i];}return x;
}1.3空间复杂度 空间复杂度也是一个数学表达式是对一个算法在运行过程中临时占用存储空间大小的量度。 空间复杂度不是程序占用了多少bytes的空间因为这个也没太大意义所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟实践复杂度类似也使用大o渐进表示法 注意:函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定 实例
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(N)呢答案是O(1)那么会有人问int *a这个指针不是指向了n个空间吗为什么复杂度不是O(N),注意空间复杂度也是一个数学表达式是对一个算法在运行过程中临时占用存储空间大小的量度。而这个数组本来就是用来存放需要排序的数据的不算额外开辟的空间。其中创建了三个变量故书简复杂度为O(N)
eg2:
long long Fac(size_t N)
{
if(N0)
return 1;
else
return Fac(N-1)*N;
}
那么这段代码的空间复杂度又是多少呢Fac(N)调用Fac(N-1),Fac(N-1)又调用了Fac(N-2),共调用了n次而每一次调用都会在函数栈帧中开辟常数个空间故空间复杂度为O(N)
eg3
#includestdio.h
long long Fib(int N)
{
if(N3)
return 1;
else
return
Fib(N-1)Fib(N-2);
}
递归调用斐波那契数的空间复杂度又是多少呢还是F(N)依次往下调用一共开辟了N个常数栈帧空间复杂度为O(N)这时又有人提出疑问了F(N)每次调用两个开辟了两个空间为什么还是O(N),这时我们需要知道时间是积累的一去不复返的空间是可以反复利用的 总结
以上便是全部内容
