seo的实现方式,学seo优化,百度站长平台工具,学校网站建设目的是什么意思第一章#xff1a;数据结构前言#xff08;Lesson 1#xff09;
1. 什么是数据结构#xff1f; 数据结构 (Data Structure) 是计算机存储、组织数据的方式#xff0c;指相互之间存在一种或多种特定关系的 数据元素的集合。 2. 什么是算法#xff1f;
算法(Algorithm)…第一章数据结构前言Lesson 1
1. 什么是数据结构 数据结构 (Data Structure) 是计算机存储、组织数据的方式指相互之间存在一种或多种特定关系的 数据元素的集合。 2. 什么是算法
算法(Algorithm):就是定义良好的计算过程他取一个或一组的值为输入并产生出一个或一组值作为输出。简单来说算法就是一系列的计算步骤用来将输入数据转化成输出结果。 第一章算法的时间复杂度和空间复杂度Lesson 2
1. 算法效率
1.1 如何衡量一个算法的好坏
long long Fib(int N)
{if (N 3)return 1;return Fib(N - 1) Fib(N - 2);
}
斐波那契数列的递归实现方式非常简洁但简洁一定好吗那该如何衡量其好与坏呢
1.2 算法的复杂度 算法在编写成可执行程序后运行时需要耗费时间资源和空间 ( 内存 ) 资源 。因此 衡量一个算法的好坏一般 是从时间和空间两个维度来衡量的 即时间复杂度和空间复杂度。 时间复杂度主要衡量一个算法的运行快慢而空间复杂度主要衡量一个算法运行所需要的额外空间。在计算机发展的早期计算机的存储容量很小。所以对空间复杂度很是在乎。但是经过计算机行业的迅速发展计算机的存储容量已经达到了很高的程度。所以我们如今已经不需要再特别关注一个算法的空间复杂度。 第二章时间复杂度
2.1 时间复杂度概念 时间复杂度的定义在计算机科学中 算法的时间复杂度是一个函数 它定量描述了该算法的运行时间。一个算法执行所耗费的时间从理论上说是不能算出来的只有你把你的程序放在机器上跑起来才能知道。但是我们需要每个算法都上机测试吗是可以都上机测试但是这很麻烦所以才有了时间复杂度这个分析方式。一个算法所花费的时间与其中语句的执行次数成正比例算法中的基本操作的执行次数为算法 的时间复杂度。 即找到某条基本语句与问题规模 N 之间的数学表达式就是算出了该算法的时间复杂度。 // 请计算一下Func1中count语句总共执行了多少次
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;前面两个for循环的时间复杂度是N*N第三个for循环的时间复杂度是2N最后一个while循环的时间复杂度是10。最终的时间复杂度函数式F(N)N*N 2*N 10 实际中我们计算时间复杂度时我们其实并不一定要计算精确的执行次数而只需要大概执行次数那么这里我们使用大O的渐进表示法。 2.2 大O的渐进表示法 大O符号Big O notation是用于描述函数渐进行为的数学符号。 推导大O阶方法 用常数1取代运行时间中的所有加法常数。F(N)N*N 2*N 10在修改后的运行次数函数中只保留最高阶项。N^2如果最高阶项存在且不是1,则去除与这个项目相乘的常数。得到的结果就是大O阶。O(N^2) F(N) N*N 2*N 10N 10F(N) 130N 100F(N) 10210N 1000F(N) 1002010 O(N^2)N 10F(N) 100N 100F(N) 10000N 1000F(N) 1000000 通过上面我们会发现大O的渐进表示法去掉了那些对结果影响不大的项简洁明了的表示出了执行次数。当N越大后面项对结果的影响就越小 另外有些算法的时间复杂度存在最好、平均和最坏情况 最坏情况任意输入规模的最大运行次数(上界) 平均情况任意输入规模的期望运行次数 最好情况任意输入规模的最小运行次数(下界) 例如在一个长度为N数组中搜索一个数据x 最好情况1次找到 最坏情况N次找到 平均情况N/2次找到在实际中一般情况关注的是算法的最坏运行情况所以数组中搜索数据时间复杂度为O(N) 2.3 常见时间复杂度计算举例 实例1 // 计算Func2的时间复杂度
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*N 10时间复杂度O(N) 在分析算法的时间复杂度时通常关注的是算法的增长趋势而不是具体的常数因子。因此当时间复杂度中出现类似2N和10N这样的情况时它们都会被认为是线性增长的即O(N)。 在大规模问题上常数因子不再影响算法的增长趋势。例如假设一个算法的时间复杂度是2N而另一个是10N如果输入规模为100时第一个算法的执行时间是200个单位时间而第二个算法的执行时间是1000个单位时间。尽管第二个算法的执行时间更长但它们的增长率是一样的都是线性增长。 因此当我们分析算法的时间复杂度时会将常数因子视为可以忽略的因素只关注随着输入规模增长时算法执行时间的增长趋势而这种增长趋势决定了算法的时间复杂度。 实例2 // 计算Func3的时间复杂度
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);
}
//时间复杂度函数式F(N) M N时间复杂度O(MN)
//M和N相互独立某一项的增加和减少都会导致时间复杂度变化所以不能省略其中一个 实例3 // 计算Func4的时间复杂度
void Func4(int N)
{int count 0;for (int k 0; k 100; k){count;}printf(%d\n, count);
}
//时间复杂度函数式F(N) 100时间复杂度O(1) - 代表常数次
//常数时间复杂度表示算法的执行时间与输入规模无关
//因此不管执行一次还是一亿次都可以认为是常数次 实例4 // 计算strchr的时间复杂度
const char * strchr ( const char * str, int character );//实现
while (*str)
{if (*str character)return str;elsestr;
}
//该算法时间复杂度O(N) 在该长度为N数组中搜索一个数据x 最好情况1次找到 最坏情况N次找到 平均情况N/2次找到在实际中一般情况关注的是算法的最坏运行情况所以数组中搜索数据时间复杂度为O(N) 实例5 // 计算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;}
}
//时间复杂度函数式F(N) N*(N-1) / 2时间复杂度O(N^2)
//第一轮n - 1次
//第二轮n - 2次
//第三轮n - 3次
//......
//倒数第二轮2次
//倒数第一轮1次
//总共n-1轮
//全部加起来就是等差数列。首项1尾项n-1项数(n-1轮)实例6 // 计算BinarySearch的时间复杂度
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;
}
//时间复杂度函数式F(N) log_2 N时间复杂度O(logN)
//每查找一次少一半所以每次除以2。N/2/2/2.../2 1
//反过来就是每次*2假设查找了x次2^x N
//查找次数和输入规模的关系就是log_2 N 12为底 实例7 // 计算阶乘递归Fac的时间复杂度
long long Fac(size_t N)
{if (0 N)return 1;return Fac(N - 1) * N;
}
//时间复杂度函数式F(N) N 1时间复杂度O(N)
//调用如下每次函数调用内部固定执行if判断和递减操作可视为O(1)
//Fac(N)
//Fac(N-1)
//Fac(N-2)
//.......
//Fac(2)
//Fac(1)
//Fac(0)实例8 // 计算斐波那契递归Fib的时间复杂度
long long Fib(size_t N)
{if (N 3)return 1;return Fib(N - 1) Fib(N - 2);
}
时间复杂度O(2^N)//调用如下
//2^0 Fib(N)
//2^1 Fib(N-1) Fib(N-2)
//2^2 Fib(N-2) Fib(N-3) Fib(N-3) Fib(N-4)
//..........
//2^(n-4) Fib(4)
//2^(n-3) Fib(3)
//2^(n-2) Fib(2)
//每一层都是上一层的2倍就是一个等比为2的等比数列
//通过下方错位相减法可得结果
//FN(n) 2^02^12^2......2^(n-4)2^(n-3)2^(n-2) 1式
//2FN(n) 2^12^2......2^(n-4)2^(n-3)2^(n-2) 2^(n-1) 2式
//两边乘以公比2再用2式减1式
//FN(n) 2^(n-1) - 1 第三章空间复杂度 空间复杂度也是一个数学表达式是对一个算法在运行过程中临时占用额外存储空间大小的量度。 空间复杂度不是程序占用了多少bytes的空间因为这个也没太大意义所以空间复杂度算的是变量的个数。空间复杂度计算规则基本跟时间复杂度类似也使用大O渐进表示法。 注意函数运行时所需要的栈空间(存储参数、局部变量、一些寄存器信息等)在编译期间已经确定好了因此空间复杂度主要通过函数在运行时候显式申请的额外空间来确定。 实例1 // 计算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;}
}
//额外的空间复杂度是常量级别的不随输入规模 n 的增加而增加
//空间复杂度为 O(1) 实例2 // 计算Fibonacci的空间复杂度
// 返回斐波那契数列的前n项
long long* Fibonacci(size_t n)
{if (n 0)return NULL;long long* fibArray (long long*)malloc((n 1) * 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;
}
//额外开辟了1个数组元素个数为n1
空间复杂度为 O(N) 实例3 // 计算阶乘递归Fac的空间复杂度
long long Fac(size_t N)
{if (N 0)return 1;return Fac(N - 1) * N;
}
//递归调用了N次开辟了N个栈帧每个栈帧使用了常数个空间。
//空间复杂度为O(N) 实例4 // 计算斐波那契递归Fib的空间复杂度
long long Fib(size_t N)
{if (N 3)return 1;return Fib(N - 1) Fib(N - 2);
}
//空间复杂度为O(N) 调用顺序为红色箭头→蓝色箭头→绿色箭头。总共开辟0~0-2层即n-1层栈帧。每一层的栈帧是共用的。例如调用Fib(2)创建栈帧返回后栈帧销毁再调用Fib(1)再创建栈帧返回销毁。
时间是累积计算的空间可以重复利用。所以空间复杂度为O(N)。
下图证明栈帧可以共用 作业
作业1
数组nums包含从0到n的所有整数但其中缺了一个。请编写代码找出那个缺失的整数。你有办法在O(n)时间内完成吗 示例 1 输入[3, 0, 1] 输出2
示例 2 输入[9, 6, 4, 2, 3, 5, 7, 0, 1] 输出8
//方法一异或
int missingNumber(int* nums, int numsSize) {int i 0;int ret 0;//0异或任何数还是任何数for (i 0; i numsSize; i)//将nums数组所有元素异或ret ^ nums[i];for (i 0; i numsSize 1; i)//因为nums数组少了个1个元素在异或完整数组ret ^ i;//相当于用完整数组和少1个元素的数组(nums数组)所有元素异或最后相同的为0//剩下的就是少了的那个元素return ret;
}//方法二两数组相减
int missingNumber(int* nums, int numsSize) {// 计算从 0 到 n 的所有整数之和int total numsSize * (numsSize 1) / 2;// 计算 nums 中所有元素的和int sum 0;for (int i 0; i numsSize; i)sum nums[i];// 返回缺失的整数return total - sum;
}//方法三排序后再比较
//排序依次查找。如果下一个数不是上一个数1那么上一个数1就是消失的数字
int missingNumber(int* nums, int numsSize) {// 如果数组只有一个数返回缺失的整数if (numsSize 1) return (nums[0] 0) ? 1 : 0;//当数组只包含一个元素时我们需要确定缺失的整数是0还是1。//因为对于一个只包含一个元素的数组而言如果这个元素是0则缺失的整数可能是1//如果这个元素不是0则缺失的整数可能是0。// 如果数组中没有0则0为缺失的整数if (nums[0] ! 0) return 0;// 遍历数组检查是否存在断号for (int i 1; i numsSize; i) if (nums[i] ! nums[i - 1] 1) // 如果下一个数不是上一个数1那么上一个数1就是缺失的整数return nums[i - 1] 1;// 如果数组中没有缺失的整数则返回数组最后一个数加一return nums[numsSize - 1] 1;
} 作业2
给定一个整数数组 nums将数组中的元素向右轮转 k 个位置其中 k 是非负数。 示例 1: 输入: nums [1, 2, 3, 4, 5, 6, 7], k 3 输出 : [5, 6, 7, 1, 2, 3, 4] 解释 : 向右轮转 1 步 : [7, 1, 2, 3, 4, 5, 6] 向右轮转 2 步 : [6, 7, 1, 2, 3, 4, 5] 向右轮转 3 步 : [5, 6, 7, 1, 2, 3, 4] 示例 2 : 输入nums [-1, -100, 3, 99], k 2 输出[3, 99, -1, -100] 解释 : 向右轮转 1 步 : [99, -1, -100, 3] 向右轮转 2 步 : [3, 99, -1, -100]
//方法一3段逆序
void reverse(int* left, int* right) {while (left right) {int tmp *left;*left *right;*right tmp;left;right--;}
}void rotate(int* nums, int numsSize, int k) {k % numsSize;reverse(nums, nums numsSize - k - 1); // 逆序前n-k个数字 4 3 2 1 5 6 7reverse(nums numsSize - k, nums numsSize - 1); // 逆序后k个数字 4 3 2 1 7 6 5reverse(nums, nums numsSize - 1); // 逆序整个数组 5 6 7 1 2 3 4
}//与上方逆序顺序不同
void rotate(int* nums, int numsSize, int k) {k % numsSize;reverse(nums, nums numsSize - 1);//逆序整个数组 7 6 5 4 3 2 1reverse(nums, nums k - 1);//逆序前k个元素 5 6 7 4 3 2 1reverse(nums k, nums numsSize - 1);//逆序后n-k个元素 5 6 7 1 2 3 4
}
//时间复杂度前n-k后k个是n逆序整个数组是n加起来是2n所以O(n)
//空间复杂度O(1)//方法二拷贝
void rotate(int* nums, int numsSize, int k) {int* tmp (int*)malloc(numsSize * sizeof(int));k % numsSize;memcpy(tmp k, nums, (numsSize - k) * sizeof(int));memcpy(tmp, nums (numsSize - k), k * sizeof(int));memcpy(nums, tmp, numsSize * sizeof(int));
}
