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

[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]

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