制作酒店网站,百度推广seo,太原有哪些做网站的公司,网站建设需要多少工种算法复杂度 算法复杂度数据结构算法算法效率复杂度的概念 数据结构
数据结构(Data Structure)是计算机存储、组织数据的⽅式#xff0c;指相互之间存在⼀种或多种特定关系的数据元素的集合。没有⼀种单⼀的数据结构对所有⽤途都有⽤#xff0c;所以我们要学各式各样的数据结…算法复杂度 算法复杂度数据结构算法算法效率复杂度的概念 数据结构
数据结构(Data Structure)是计算机存储、组织数据的⽅式指相互之间存在⼀种或多种特定关系的数据元素的集合。没有⼀种单⼀的数据结构对所有⽤途都有⽤所以我们要学各式各样的数据结构如线性表、树、图、哈希等
算法
算法就是定义良好的计算过程他取⼀个或⼀组的值为输⼊并产⽣出⼀个或⼀组值作为输出。简单来说算法就是⼀系列的计算步骤⽤来将输⼊数据转化成输出结果。
算法效率
算法是有好坏优劣之分的这就牵扯复杂度的概念
复杂度的概念
衡量⼀个算法的好坏⼀般是从时间和空间两个维度来衡量的即时间复杂度和空间复杂度。
时间复杂度主要衡量⼀个算法的运⾏快慢⽽空间复杂度主要衡量⼀个算法运⾏所需要的额外空间。 我们给出以下例子 void rotate(int* nums, int numsSize, int k) {while(k--){int tmp nums[numsSize - 1];for(int i numsSize - 1;i 0;i--){nums[i] nums[i-1];}nums[0] tmp;}}当我们写下以上代码时提交发现会给出超出时间限制的提示。
此时证明我们写下的代码的时间复杂度是不符合要求的 经过思考后我们想到可以创建一个临时数组来存放轮转k次后所得的元素然后将临时数组的元素再赋给原数组这样我们就只需独立的遍历数组时间复杂度就降低到了O(n)但是因为我们又申请了新的空间来存放元素那么我们的空间复杂度就同样为O(n)这是一种以空间换取时间的方法
void rotate(int* nums, int numsSize, int k) {//创建与原数组大小相等的新数组int newArr[numsSize];//遍历数组将原数组的元素放入新数组中for(int i 0;i numsSize;i){//向右轮转k次(ik)%numsSize对应位置刚好是我们想要的newArr[(ik)%numsSize] nums[i];}for(int i 0;i numsSize;i){//将临时数组的元素放入原数组中nums[i] newArr[i];}
}那么还有没有其他的方法来完成题目要求呢 方法是三次逆置。 即先对数组元素进行整体逆置然后数组以有效轮转次数k为分界将数组分为前后两个部分再对前后两个部分分别逆置得到的数组就是符合要求的。此时的时间复杂度为O(n)空间复杂度为O1。
void swap(int* x,int* y)
{//交换元素int t *x;*x *y;*y t;
}void reverse(int* nums,int a,int b)
{while(a b){swap(nums[a],nums[b--]);}
}void rotate(int* nums, int numsSize, int k) {//k是轮转的有效次数k % numsSize;reverse(nums,0,numsSize-1);reverse(nums,0,k-1);reverse(nums,k,numsSize-1);
}
