algorithm - 一个关于时间复杂度定义的谜题

Question

维基百科定义 time complexity作为

In computer science, the time complexity of an algorithm quantifies the amount of time taken by an algorithm to run as a function of the length of the string representing the input.

强势部分是什么意思？

我知道算法可以被视为一个函数，但 为什么它的输入必须是 “代表字符串的长度”？

Answer 1

加粗部分的函数表示算法的时间复杂度，不是算法本身。算法可以用具有函数关键字的编程语言实现，但那是另一回事。

算法 MergeSort 的输入是一个 32m 位的列表(假设 m 个 32 位值)。它的时间复杂度 T(n) 是输入大小 n = 32m 的函数，在最坏的情况下由 O(n log n) 从上面限制。 MergeSort 可以作为 C 或 JavaScript 中的函数来实现。