这是考察的哪种数据结构？

[LuckyPocketWatch]

这周抽时间去了某家公司面试，面试先让做一些题目，其中一条如下

假设 x 的值范围[0,255]，现在有多项式 f(n) = An + Bn * C^x;其中 An 和 Bn 是根据 n 的值而变化，C 为固定值,而 x 的值会根据 n 的值随机选择[0,255]中的一个值。假设有 50 亿个这样的多项式，需要求多项式和，既求 f(0)+f(1)+...+f(50 亿),问：如何通过变化多项式来减少计算次数？

C^x 表示 C 的 x 次方，下同

这题目我直接没写，我不知道如何变化多项式来减少计算次数，笔试完面试的人让我再次看下这条题目，问能不能再想下，我想了一会实在想不出答案，老实回答不知道。然后面试的人表示我对数据结构这块比较欠缺，然后他告诉了我正确答案：

由于 x 的范围是[0,255]，而 C 是一个常量，所以可以构建一个数组，包含 255 个值，对应 C^0,C^1,C^2...C^255 ，这样每次计算 f(n)的值的时候，就不用每次都计算 C^x ，而只需要根据 x 的值，从数组中查找对应的值即可。通过这种方法，原本需要计算 50 亿次的 C^x 的值，现在只需要提前计算 255 次 C^x 的值，然后每次需要的时候去数组中提取即可

我想问下，这条题目是考察的哪种数据结构？

[hsfzxjy]

这就是单纯的打表吧。。这也不叫“变化多项式”

[y1y1]

所以这个答案怎么变化的多项式？

[hello2090]

空间换时间啊，他都说了 50 亿次了不是很明显么，你总不能死算 50 亿次吧

[timethinker]

题目有点迷惑，不过以空间换时间应该算是基本操作，但是跟数据结构感觉也沾不上边呀，为何说数据结构欠缺呢？

[liprais]

even better:你还可以构建个矩阵一次把所有数据算出来给他
这面试官水平不咋地

[smallboy19991231]

数组也算数据结构了？

[swulling]

如果原题就是这样的话，证明面试官水平不好。 [x 的值会根据 n 的值随机选择[0,255]中的一个值。]

你可以让面试官介绍下，什么叫做 [根据 n 的值随机] 。

[LuckyPocketWatch]

@swulling

他的意思是，x 是个随机值，n 类似种子，n 的值不同，x 会随机到[0,255]内的任意一个值

[swulling]

@LuckyPocketWatch 为啥要用 N 做种子，你随便找个种子，随机数生成器每次生成的值就是随机的。

[LuckyPocketWatch]

@hello2090

所以这是哪个数据结构。。。。

[swulling]

一个简简单单的查表法，整这么多铺垫，也是很有意思。

而且算的还是浮点数指数运算这种 O(1)的活（不可能是整数运算，255 次方都存不下）。

[me1onsoda]

@smallboy19991231 那算什么

[me1onsoda]

说实话没看懂题，如果你要考察数据结构，是要体现出某个数据结构的特性，我没看出来这里用了数组哪个特性。
我觉得这人在卖弄

[me1onsoda]

@hello2090 按照他给的答案，这里还是要算 50 亿次

[nkidgm]

老了老了，数据结构的题目直接略过。。

脑袋里只保留基本的数组，链表，栈，队列，图，树，堆等几个基本概念和性质，外加部分查找算法和主流排序算法。。。

[GeruzoniAnsasu]

……那还不是要算 50 亿次 An+Bn*Carray[n] ？

[tyrantZhao]

这啥破题。。。

[antonius]

更应该称作为 f(n) = An + Bn * C^x ，x=g(n)，x∈[0,255]。这题出的不严谨，也不漂亮。也不是“通过变化多项式来减少计算次数”。

[janwarlen]

数据结构 动态规划

> 通常许多子问题非常相似，为此动态规划法试图仅仅解决每个子问题一次，从而减少计算量：一旦某个给定子问题的解已经算出，则将其记忆化存储，以便下次需要同一个子问题解之时直接查表。这种做法在重复子问题的数目关于输入的规模呈指数增长时特别有用。

[janwarlen]

应该是算法而不是数据结构了

[changnet]

这题目误导人啊。我看了题目，主要是有 50 亿个这样的多项式，要求是通过变化多项式来减少计算次数。

我首先想的是有什么算法可以合并这些式子，一次算出来，类似于奥数的多项式合并。

所以算法应该是如何让这 50 亿次快速算出来，而不是去关注这多项式里的 C^x 如何优化。因为即使优化了这一小部分，还是需要 50 亿的计算。

面试题就应该要突出考查的重点。结果就考了个缓存，50 亿的计算量一个没少，真是考了个寂寞。

[hello2090]

@me1onsoda 既然 50 亿个方程，那肯定要算 50 亿次，但每次的 C^X 只要读出来，不用每次都算了啊

[ccde8259]

答 Cache 掉 C^x 都算对……