把网站提交给百度,wordpress 主题盗,怎么在互联网推广产品,中建八局一公司总部在哪数据结构可以简单理解为在内存中管理数据
它具有速度快 带电存储的特点#xff08;临时存储#xff09; 如何衡量一个算法的好坏
因此衡量一个算法的好坏#xff0c;一般是从时间和空间两个维度来衡量的#xff0c;即时间复杂度和空间复杂度。
时间复杂度主要衡量一个算…数据结构可以简单理解为在内存中管理数据
它具有速度快 带电存储的特点临时存储 如何衡量一个算法的好坏
因此衡量一个算法的好坏一般是从时间和空间两个维度来衡量的即时间复杂度和空间复杂度。
时间复杂度主要衡量一个算法的运行快慢
而空间复杂度主要衡量一个算法运行所需要的额外空间 1.时间复杂度
1.1时间复杂度的概念
算法的时间复杂度是一个表达式算法中的基本操作的执行次数为算法的时间复杂度 1.2 大O的渐进表示法
大O符号Big O notation是用于描述函数渐进行为的数学符号。 如何推导出O
1、用常数1取代运行时间中的所有加法常数。
2、在修改后的运行次数函数中只保留最高阶项。
3、如果最高阶项存在且不是1则去除与这个项目相乘的常数。得到的结果就是大O阶。
那么前面的F(N)N^22N10 的复杂度也就是 O(N^2) 另外有些算法的时间复杂度存在最好、平均和最坏情况 最坏情况任意输入规模的最大运行次数(上界) 平均情况任意输入规模的期望运行次数 最好情况任意输入规模的最小运行次数(下界)
例如在一个长度为N数组中搜索一个数据x 最好情况1次找到 最坏情况N次找到 平均情况N/2次找到
在实际中表示时间复杂度一般情况关注的是算法的最坏运行情况所以数组中搜索数据时间复杂度为O(N) 1.3关于时间复杂度的举例
例题一
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);
}例题二
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);
}例题三
void Func4(int N)
{int count 0;for (int k 0; k 100; k){count;}printf(%d\n, count);
} 例题四
// 计算strchr函数的时间复杂度
const char* strchr(const char* str, int character); 例题五冒泡排序算法的时间复杂度
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;}
}例题六二分查找
一定要注意二分查找的前提是有序
int BinarySearch(int* a, int n, int x)
{assert(a);int begin 0;int end n - 1;// [begin, end]begin和end是左闭右闭区间因此有号while (begin end){int mid begin ((end - begin) 1);if (a[mid] x)begin mid 1;else if (a[mid] x)end mid - 1;elsereturn mid;}return -1;
}例题七关于阶乘 long long Fac(size_t N)
{if (0 N)return 1;return Fac(N - 1) * N;
} 例题八 例题九斐波那契数
long long Fib(size_t N)
{if (N 3)return 1;return Fib(N - 1) Fib(N - 2);
} 1.4关于一道题目. - 力扣LeetCode消失的数字
这道题主要有两种解法
方法一利用等差数列求和的方法找出消失的数字
int missingNumber(int* nums, int numsSize) {//numsSize就是最大的那个数也就是缺失的数一定小于numsSizeint n numsSize;//利用等差数列0,1,2,3,....n// 首项加尾项 再乘总项数 最后再除2int sum (0n) * (n1) / 2;int i 0;int sum10;for(i0;in;i){sum1sum1*(numsi);}int rst sum-sum1;printf(%d\n,rst);return rst;
} 方法二:利用异或符号来求出缺失的数字
int missingNumber(int* nums, int numsSize) {int i0;int x0;for(i0;inumsSize;i)//numsize表示的是数组的元素个数如果是9那么就是0到9之间缺了一个元素{xx^nums[i];}for(i0;inumsSize;i)//0到9之间的所有数字{xx^i;}return x;
} 2.空间复杂度
2.1空间复杂度的概念
空间复杂度也是一个数学表达式是对一个算法在运行过程中临时额外占用存储空间大小的量度
空间复杂度不是程序占用了多少bytes的空间因为这个也没太大意义所以空间复杂度算的是变量的个数。
空间复杂度计算规则基本跟时间复杂度类似也使用大O渐进表示法。 函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了
因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。 2.2关于空间复杂度的举例
例题一冒泡排序算法的空间复杂度
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;}
}例题二
long long* Fibonacci(size_t n)
{if(n0)return NULL;long long * fibArray (long long *)malloc((n1) * sizeof(long long));fibArray[0] 0;fibArray[1] 1;for (int i 2; i n ; i){fibArray[i] fibArray[i - 1] fibArray [i - 2];}return fibArray;
} 例题三
long long Fac(size_t N)
{if(N 0)return 1;return Fac(N-1)*N;
} 例题四 两道练习题
练习一 旋转数组OJ链接. - 力扣LeetCode
方法一
这个方法因为超时而错误
void rotate(int* nums, int numsSize, int k) {int tmp 0;int i 0;while (k 0){tmp nums[numsSize - 1];for (i 0; i numsSize - 1; i)//i从0到5{nums[numsSize - 1 - i] nums[numsSize - 2 - i];}nums[0] tmp;k--;}for (i 0; i numsSize; i){printf(%d , nums[i]);}
}
方法二
void fun(int* nums, int left, int right)
{while (left right){int tmp 0;tmp nums[left];nums[left] nums[right];nums[right] tmp;left;right--;}
}void rotate(int* nums, int numsSize, int k) {int N numsSize;k k % N;//先把前N-k个逆置fun(nums, 0, N - k - 1);//后k个逆置fun(nums, N - k, N - 1);//整体逆置fun(nums, 0, N - 1);int i 0;for (i 0; i numsSize; i){printf(%d , nums[i]);}
}
方法三 #includestdio.h
#includestdlib.h
void rotate(int* nums, int numsSize, int k) {int* pf(int*)malloc(numsSize*sizeof(int));if(pfNULL){perror(malloc);}kk%numsSize;int i0;int j0;for(inumsSize-k;inumsSize;i)//i取4到6{pf[j]nums[i];j;}for(i0;inumsSize-k;i)//i取0到3{pf[j]nums[i];j;}for(i0;inumsSize;i){nums[i]pf[i];}
} 练习二移除元素OJ链接. - 力扣LeetCode
int removeElement(int* nums, int numsSize, int val) {int i 0;int j 0;for (i 0; i numsSize; i) {if (nums[i] val){continue;}nums[j] nums[i];j;}return j;
}
