个人网站主页设计模板,网络营销的基本特点和描述,网站后端开发软件,建设网站考虑因素1.数据结构前言
下面的概念有的比较难理解#xff0c;做个了结就行。
1.1数据结构的起源
在现实生活中我们更多地并不是解决数值计算的问题#xff0c;而是 需要一些更科学的手段如#xff08;表#xff0c;数#xff0c;图等数据结构#xff09;#xff0c;才能更好…1.数据结构前言
下面的概念有的比较难理解做个了结就行。
1.1数据结构的起源
在现实生活中我们更多地并不是解决数值计算的问题而是 需要一些更科学的手段如表数图等数据结构才能更好地处理问题。所以数据结构是一门研究非数值计算的程序设计问题中的操作对象以及他们之间的关系和操作等相关问题的学科。
1968年美国高德纳教授在其所写的《计算机程序设计艺术》第一卷《基本算法》中较系统的阐述了数据的逻辑结构及其操作。
1.2数据结构Data Structure的定义
数据结构相互之间存在一种或者多种关系的数据元素的集合
数据元素是组成数据的有一定意义的基本单位在计算机中被当做成体处理。也叫做记录。比如在人类社会中它的数据元素就是人。畜类中牛羊猪等就是它的数据元素。
数据项一个数据元素可以由多个数据项组成。比如人的数据项可以由眼睛、鼻子、嘴巴等等。
数据对象具有相同性质的数据元素的集合是数据的子集。比如人都有生日、姓名、性别把这些拥有相同数据项的数据元素就称为相同性质的数据元素。 1.3逻辑结构与物理结构
1.3.1逻辑结构
逻辑结构数据元素之间的相互关系。
常见的逻辑结构
集合结构”平等“ 线性结构一对一 树形结构一对多 图形结构多对多 1.3.2物理结构
物理结构指的是数据的逻辑结构在计算机中的存储方式
存储结构的分类顺序存储结构、链式存储结构
顺序存储结构把数据元素存放在连续的内存空间中这种的结构的物理结构与逻辑结构是相同的 链式存储结构把数据元素存放在任意的内存空间中这个任意可以连续也可以不连续。
这种存储结构的操作是建立在指针域上的因为你总得通过一个手段去找到这些元素。 1.4抽象数据类型
1.4.1数据类型
数据类型只一组具有相同性质的值的集合以及定义在此集合上面的一组操作的总称。
高级语言中类型往往指代的是变量、常量、表达式所能表示的范围还有所能进行的 - * /等一系列操作。
在C语言中数据类型分为
原子类型不可再分的基本单位包括整形、浮点型、字符型
结构类型由若干个类型组合而成可以再分。比如一个整形数组就包含若干个整形数据。
1.4.2抽象数据类型
抽象是指抽出事物具有的本质属性。
抽象数据类型是指一个数学模型以及定义在该模型上面的一组操作。
对于抽象数据类型我们并不关注数据本身的物理结构而是关注它的数学抽象特征。
一个抽象数据类型定义了一个数据对象、数据元素中各数据元素之间的关系及对数据的操作。
2.算法的复杂度
在次之前我们先看一个例题189. 轮转数组 - 力扣LeetCode 经过考虑我们可以有三种解法
1.挨个轮转
void rotate(int* nums, int numsSize, int k) {int i0;while(k--){int tmpnums[numsSize-1];for(inumsSize-1;i0;i--){nums[i]nums[i-1];}nums[0]tmp;}
} 2.取余挨个轮转
void rotate(int* nums, int numsSize, int k) {int i0;k%numsSize;while(k--){int tmpnums[numsSize-1];for(inumsSize-1;i0;i--){nums[i]nums[i-1];}nums[0]tmp;}
} 3.面向结果编程
void rotate(int* nums, int numsSize, int k) {int ans[numsSize];int i0;for(i0;inumsSize;i){ans[(ik)%numsSize]nums[i];}for(i0;inumsSize;i){nums[i]ans[i];}}4.三次逆序法
void Reverse(int* nums,int low,int high){while(lowhigh){int tmpnums[low];nums[low]nums[high];nums[high]tmp;low;high--;}
}
void rotate(int* nums, int numsSize, int k) {k%numsSize;Reverse(nums,0,numsSize-k-1);Reverse(nums,numsSize-k,numsSize-1);Reverse(nums,0,numsSize-1);}2.1时间复杂度
先说明一下上述方法的1、2的关系为优化。3、4是使用了不同的算法。
2.1.1时间复杂度的定义
时间复杂度在进行算法分析时语句总的执行次数Tn是关于问题规模n的函数进而分析Tn随n的变化情况并确定T(n)数量级。算法的时间复杂度也就是算法的时间量度记作T(n)O(f(n))。它表示随着问题规模n的增大算法的执行时间的增长率和符fn的增长率相同称作算法的渐进时间复杂度简称时间复杂度。其中符fn是问题规模n的某个函数。 这里我们从定义中提取几个关键点
1.算法时间复杂度是算法渐进时间复杂度的简称。
2.它表示的是一种变化趋势随问题规模或者增长率。
3.并不是一个确切的语句到底执行多少次的函数表达式。
2.1.2算法时间复杂度的大O渐进表示法 大O符号Big O notation是用于描述函数渐进行为的数学符号 推导⼤O阶规则 1. 时间复杂度函数式 T(N) 中只保留最⾼阶项去掉那些低阶项因为当 N 不断变大时 低阶项对结果影响越来越小当 N 无穷大时就可以忽略不计了。 2. 如果最高阶项存在且不是 1 则去除这个项目的常数系数因为当 N 不断变大这个系数 对结果影响越来越小当 N 无穷大时就可以忽略不计了。 3. T(N) 中如果没有 N 相关的项目只有常数项用常数 1 取代所有加法常数。 2.1.3算法时间复杂度的例题
2.1.3.1
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);
}
Tn2*n10只关注循环的额外开销
时间复杂度O(n)
2.1.3.2
void Func3(int N, int M)
{
int count 0;
for (int k 0; k M; k)
{
count;
}
for (int k 0; k N ;
k)
{
count;
}
printf(%d\n, count);
}
同样的时间复杂度O(n)
2.1.3.3
void Func4(int N)
{
int count 0;
for (int k 0; k 100; k)
{
count;
}
printf(%d\n, count);
}
O(1)
2.1.3.4
const char * strchr ( const char
* str, int character)
{
const char* p_begin s;
while (*p_begin ! character)
{
if (*p_begin \0)
return NULL;
p_begin;
}
return p_begin;
}
这是一个查找某个字符的算法但是不同情况有不同的复杂度有不同划分
假设要找的就在第一个字符位置或常数个T(n)k(常数) -- O(1)4
假设要找的在最后一个位置T(n)n -- O (n)
假设要找的在中间T(n)n/2 -- O(n) 2.1.3.5
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;
}
}
T(n)N*(N1)/2 --O(n)n^2
2.1.3.6
void func5(int n)
{
int cnt 1;
while (cnt n)
{
cnt * 2;
}
}
O(n)logn 这里写成lnn lgn都行因为我们说时间复杂度表示的是变化率所以只需要表示出来对数阶就可以。
2.1.3.7
递归的时间复杂度
// 计算阶乘递归Fac的时间复杂度
long long Fac(size_t N)
{
if(0 N)
return 1;
return Fac(N-1)*N;
}
O(n)n 递归时间复杂度的求法单次递归的时间复杂度*递归次数 2.1.4常见的时间复杂度 2.2.空间复杂度 空间复杂度也是⼀个数学表达式是对⼀个算法在运⾏过程中因为算法的需要额外临时开辟的空间。空间复杂度不是程序占⽤了多少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) 3.轮转数组复杂度分析 法一O(n^2) O(1) 法二O(n^2) O(1) 法三O(n) O(n) 法四O(n) O(1) 完
