DSA PA1 REPORT

CST 1-2 Graphics Report

算法构思

交点的个数问题可以转化成该点所在区域（考虑到没有线段相交这个条件）即可，因此此算法实现分为两步：对x、y点的排序以确定每条线段和查找确定点所在的区域。

排序实现参考了课本中的归并排序算法来实现，不同处在于一次实现了x和y两个数组的排序（两个数组大小一样所以每次划分的左右两段长度也一样，可以在一个函数中实现）

查找时基于二分查找的思路，确定点的区域时每次比较时利用了叉乘进行判断，从而避免出现除法，考虑到数据范围会超出int，判断时使用long long数据类型，同时还需考虑边界情况（位于最左侧线段的左侧和最右侧线段的右侧）

时间和空间复杂度的估算

时间复杂度：归并排序算法复杂度为 $O(nlogn)$，二分查找每次算法复杂度为 $ O( log (n) ) $ ，总复杂度为 $O((n+m)logn)$

空间复杂度：全局变量x_0和y_0存储了坐标轴上的点的信息，占用空间为2n，归并排序每次合并时新开了x_1和y_1数组，合并后会立即删除，不会保留到之后的合并中，占用空间为2n，二分查找本身不占用空间，因此总空间占用为$O(n)$

CST 1-3 filename Report

算法构思

因为“插入字符”和“删除字符”操作实际上是可以交换顺序的，所以每种从A到B之间的变换，实际上都可以转换成从A删除字符到A和B的某个公共子序列，然后再插入字符直到得到B。要求k步内能否从A变成B，实际上就是用动态规划方法求A和B最长公共子序列的问题。

实现过程中遇到的问题

具体实现时需要解决以下几个问题：1.由于500000*500000会超过存储空间范围，查询网络后发现可以采用滚动数组方法，转换为2*500000大小的数组。2.使用一般的求公共子序列算法会超时，但考虑到k步的限制，所以每次不需要枚举500000次，而只需要看$((n > m ? n - m : m - n) + k) / 2 + 1$范围内即可（相当于只用看对角线附近的）。

时间和空间复杂度的估算

时间复杂度：DP是算法的关键，时间复杂度为 $O(kn)$（不妨令n>m，$ n \leq 501000 $）

空间复杂度：主要占用空间的为memo数组，大小为2*501010，和两个长为501000的char数组，因此算法空间复杂度为$O(n)$