算法题（不是我的作业），老师没时间，然后希望我帮她做一下，然而我看了两节课依旧一头雾水，只能麻烦各位 v 友懂的给点提示，只要思路就行。

[NightVermouth]

http://wwwf.imperial.ac.uk/~drmii/M3SC_2016/Exer_3_2016.pdf

[holyzhou]

看不懂 但我能说 ，作业正文的第一句话亮了嘛？ 老外治学这么严谨啊

[hzm0318hzm]

看着头晕， mark 下看有没大神给你解决

[seki]

这是个大作业，但是已经是循序渐进地分好了每一步
你是从哪一步开始没有思路？

[stackpop]

https://people.sc.fsu.edu/~jburkardt/cpp_src/sine_transform/sine_transform.html

[stackpop]

http://www-personal.umich.edu/~mejn/computational-physics/dcst.py

[NightVermouth]

@seki 我说一下我对题目的理解吧，首先我高数还没学到傅立叶变换，这可能对我理解题目会造成偏差，题中的对 y 的分解我就无法理解。我理解的内容是，为了缩减时间复杂度，需要对矩阵 S 进行降维，分成 N/2 维的 S ，以及 N/2 维的 T ， T 可以再降维成 N/4 的 T ，及 N/4 的 U ， U 还可以进行降维（这一步怎么做到我没理解）。降维过程递归进行，最后当 N/2^l 为基数时停止，然后把底层的小矩阵算出来，大矩阵根据小矩阵得出（动态规划的思想？），然后计算对应的 Xi 。
以上是我的理解。然后题目第一题我就一头雾水。。。

[GtDzx]

大概就是让你算 x=SN*y ，其中 x,y 是(N-1)维的向量， SN 是 N-1xN-1 的矩阵。暴力去乘就是 O(N^2)的。

让后他介绍了一种递归分治的 O(NlogN)算法。大概思路就是把 x 分成两组， x2,x4,x6,x8... 这一组可以直接用 S_{N/2}*a ， x1,x3,x5,x7...这一组可以用 T_{N/2}*s 求出来（其中 T,a,s 都在文中有定义）。

这样我们就把 x=SN*y 分解为 2 个一半规模的小问题 x=S_{N/2}*y 和 x=T_{N/2}*y 。比较郁闷的是 x=TN*y 是一个新问题。幸好这个问题也有递归分治的解法。 x=TN*y 可以被分解为 x=T_{N/2}*y 和 x=U_{N/2}*y 两个规模一般的小问题。但是这里又引入了一个新问题 x=UN*y 。不过这个问题也是能分解的，可以分解为 x=T_{N/2}*y 和 x=T_{N/2}*y 两个子问题。到这里终于没有再引入新问题了。于是整个问题可以在 O(NlogN)解决。

[seki]

@NightVermouth
我就看了一下前言还有第一题， DST 就是将一个向量分解为多个带 sin 值的向量序列，你可以把它类比于泰勒展开……
第一题是给定一个数字 n ，然后输出一列双精度向量，分别是各个 sin 值，用在后边的计算当中当作 sin 值表，避免重复求同一个 sin 值
剩下的我觉得楼上说得挺好的了，就是需要补一点矩阵的知识，比如向量与矩阵的乘法是如何计算的等等，这个可以看线性代数

[seki]

第 2 题是让你实现选出来的子向量与各个矩阵的乘法，矩阵的各个元素的值在 summary 中给出了。看样子在这里需要写分治递归，这两题中的 N =1 × 2^m

第 3 题是考虑 N = 3 × 2^m 的情况

第 4 题是算法分析

第 5 题和前面的作业有关，放弃了……

第 6 题是扩展到 N=5 × 2^m 的情况

[cpygui]

这题占 40%的期末总成绩！这题要是挂了是不是就挂科了？
她不去 office hour 吗？

[NightVermouth]

@cpygui 我也不知道啊， 40%你是从哪里看到的？

[cpygui]

@NightVermouth http://wwwf.imperial.ac.uk/~drmii/M3SC_2016/
好像还有一场 seminar 讨论之后，她从来不参加讨论的吗？

[aprikyblue]

一脸懵逼

[msg7086]

@holyzhou 抄袭作业但不署名是重罪。

[NightVermouth]

@cpygui 我也不清楚，这题目只是交给我做一下，至于来龙去脉我并不知道。貌似是某个人拜托我老师解决，然后老师没空，就推到了我这里（这些是我猜的）。。。

[rubytek]

这是数字信号处理的课后题吧。。算法？

[cpygui]

@NightVermouth 伦敦帝国理工算是世界顶级名校啊，当初这人是怎么混进去的(๑>؂<๑）

真要是做不来，问 TA 或者教授。不过按你说的，这特么还是层层转包给你的。。。。你和这人没瓜葛，帮别人做题有意思么？

要是有好事者把这个帖子举报给讲师就好玩了，哈哈哈

[Andiry]

在这里问算是作弊吧？

[NightVermouth]

@cpygui 我做题是出于兴趣，不过听你这么一说，我还是推掉比较好。但这题拿来钻研，锻炼思维对我来说还是蛮不错的。

[NightVermouth]

@Andiry 从我的角度讲，算请教或者探讨更为合适吧，毕竟这不是我的作业，谈不上作弊抄袭。