算法题（不是我的作业），老师没时间，然后希望我帮她做一下，然而我看了两节课依旧一头雾水，只能麻烦各位 v 友懂的给点提示，只要思路就行。
NightVermouth · 2016-04-21 16:46:58 +08:00 · 5195 次点击这是一个创建于 3173 天前的主题，其中的信息可能已经有所发展或是发生改变。
 |
1
holyzhou 2016-04-21 16:58:01 +08:00
看不懂 但我能说 ，作业正文的第一句话亮了嘛？ 老外治学这么严谨啊
|
 |
2
hzm0318hzm 2016-04-21 17:13:28 +08:00
看着头晕， mark 下看有没大神给你解决
|
 |
3
seki 2016-04-21 17:31:27 +08:00
这是个大作业，但是已经是循序渐进地分好了每一步
你是从哪一步开始没有思路？ |
 |
4
stackpop 2016-04-21 17:36:44 +08:00
|
|
5
stackpop 2016-04-21 17:37:08 +08:00
|
 |
6
NightVermouth OP @seki 我说一下我对题目的理解吧，首先我高数还没学到傅立叶变换，这可能对我理解题目会造成偏差，题中的对 y 的分解我就无法理解。我理解的内容是，为了缩减时间复杂度，需要对矩阵 S 进行降维，分成 N/2 维的 S ，以及 N/2 维的 T ， T 可以再降维成 N/4 的 T ，及 N/4 的 U ， U 还可以进行降维（这一步怎么做到我没理解）。降维过程递归进行，最后当 N/2^l 为基数时停止，然后把底层的小矩阵算出来，大矩阵根据小矩阵得出（动态规划的思想？），然后计算对应的 Xi 。
以上是我的理解。然后题目第一题我就一头雾水。。。 |
 |
7
GtDzx 2016-04-21 18:11:25 +08:00  1
大概就是让你算 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)解决。 |
|
8
seki 2016-04-21 20:49:30 +08:00 1
@NightVermouth
我就看了一下前言还有第一题， DST 就是将一个向量分解为多个带 sin 值的向量序列，你可以把它类比于泰勒展开…… 第一题是给定一个数字 n ，然后输出一列双精度向量，分别是各个 sin 值，用在后边的计算当中当作 sin 值表，避免重复求同一个 sin 值 剩下的我觉得楼上说得挺好的了，就是需要补一点矩阵的知识，比如向量与矩阵的乘法是如何计算的等等，这个可以看线性代数 |
|
9
seki 2016-04-21 21:12:22 +08:00
第 2 题是让你实现选出来的子向量与各个矩阵的乘法，矩阵的各个元素的值在 summary 中给出了。看样子在这里需要写分治递归，这两题中的 N =1 × 2^m
第 3 题是考虑 N = 3 × 2^m 的情况 第 4 题是算法分析 第 5 题和前面的作业有关，放弃了…… 第 6 题是扩展到 N=5 × 2^m 的情况 |
 |
10
cpygui 2016-04-21 21:31:14 +08:00
这题占 40%的期末总成绩！这题要是挂了是不是就挂科了？
她不去 office hour 吗？ |
|
11
NightVermouth OP @cpygui 我也不知道啊， 40%你是从哪里看到的？
|
|
12
cpygui 2016-04-21 22:00:10 +08:00
|
 |
13
aprikyblue 2016-04-21 22:12:10 +08:00 via Android
一脸懵逼
|
|
15
NightVermouth OP @cpygui 我也不清楚，这题目只是交给我做一下，至于来龙去脉我并不知道。貌似是某个人拜托我老师解决，然后老师没空，就推到了我这里（这些是我猜的）。。。
|
 |
16
rubytek 2016-04-22 00:24:05 +08:00
这是数字信号处理的课后题吧。。算法？
|
|
17
cpygui 2016-04-22 01:02:36 +08:00 via Android
@NightVermouth 伦敦帝国理工算是世界顶级名校啊，当初这人是怎么混进去的(๑><๑）
真要是做不来，问 TA 或者教授。不过按你说的，这特么还是层层转包给你的。。。。你和这人没瓜葛，帮别人做题有意思么？ 要是有好事者把这个帖子举报给讲师就好玩了，哈哈哈 |
 |
18
Andiry 2016-04-22 01:12:03 +08:00
在这里问算是作弊吧？
|
|
19
NightVermouth OP @cpygui 我做题是出于兴趣，不过听你这么一说，我还是推掉比较好。但这题拿来钻研，锻炼思维对我来说还是蛮不错的。
|
|
20
NightVermouth OP @Andiry 从我的角度讲，算请教或者探讨更为合适吧，毕竟这不是我的作业，谈不上作弊抄袭。
|
|
21
NightVermouth OP @rubytek 有算法的内容，比如需要用到分治策略
|
|
22
cpygui 2016-04-22 01:29:01 +08:00 via Android
@NightVermouth (ಡωಡ)hiahiahia 那我能不能出于兴趣把这人举报？
|
|
23
NightVermouth OP @cpygui 出于兴趣，你可以。。。 xD
|
 |
26
paulagent 2016-04-22 05:15:37 +08:00 via Android
如果被人举报这孩子就完了，澳洲不是刚刚有个被人举报了，因为 wuwei 那事
|
|
27
cpygui 2016-04-22 06:13:14 +08:00 via Android
@shiji 嘻嘻嘻，你肯定不知道西方有些学校不收学费的吧，国际生也不收。不过要是能花钱进 mit ，我还是愿意的
|
 |
28
tempdban 2016-04-22 06:38:51 +08:00 via Android
兄弟我时间有限只看了一眼,没猜错的话…骑士应该就是 FFT 吧
|
 |
29
Tink 2016-04-22 08:22:33 +08:00 via iPhone
我的高数跟没学一样
|
|
30
NightVermouth OP @tempdban 维基百科上说是该算法类似于 FFT,然而我并不知道 FFT 是什么。。。我才大一，高数课还没到这部份内容。
|
 |
31
proudzhu 2016-04-22 09:40:46 +08:00 via Android
@NightVermouth 然而 FFT 是 DSP 的内容，不是高数
|
|
32
NightVermouth OP @proudzhu 软件专业的表示不明觉厉。只是知道高数中有个傅立叶， DSP 又有跟傅立叶转换与关系，就想当然地联系在一起了 xD
|
|
33
tempdban 2016-04-22 18:57:07 +08:00 via Android
@NightVermouth 简单介绍一下，傅里叶变换可以把一个和时间有关的函数,转换成和频率有关的函数，但是要求函数是连续的，套用连续函数傅里叶变换的定义，还有个离散傅里叶变换(dft)，可以对离散函数进行傅里叶变换，但是按照一般的算法太慢了，数学家们又研究出来可以进行快速傅里叶变换的方法，叫 fft
|
|
34
NightVermouth OP @tempdban soga 谢谢
|
Select Language