算法与输入大小是线性的 (O(n))，但如果输入大小是指数的呢？
Algorithm is linear (O(n)) to size of input, but what if input size is exponential
讲师说算法的复杂度通常是根据其输入大小来衡量的。
所以，当我们说一个算法是线性的，那么即使你给它一个 2^n 的输入大小（假设 2^n 是二叉树中的节点数），该算法仍然是线性的输入大小？
以上好像是导师的意思，但我脑子里转不过来。如果你给它一个 2^n 输入，它是某个参数“n”的指数，然后称这个输入为“x”，那么，当然，你的算法对 x 是线性的。但在内心深处，它不仍然是“n”的指数吗？说它对 x 是线性的有什么意义？
如果算法具有线性time-complexity，则无论输入大小如何，它都是线性的。无论是固定大小的输入，二次还是指数。
显然 运行 固定大小数组、二次或指数的算法将花费不同的时间，但复杂度仍然是 O(n)。
也许这个例子会帮助你理解，运行 merge-sort 在大小为 16 的数组上意味着 merge-sort 是 O(1) 因为它需要不断的操作来排序大批？答案是否定的。
当我们说算法是 O(n) 时，意味着如果输入大小是 n，它与输入大小成线性关系。因此，如果 n 是另一个参数 k 的指数（例如 n = 2^k），则该算法对于输入大小也是线性的。
另一个例子是对大小为 n 的输入数组进行二进制搜索的时间复杂度。我们说对大小为 n 的排序数组的二进制搜索在 O(log(n)) 中。这意味着关于输入大小，它最多需要渐近 log(n) 比较来搜索大小为 n、
的输入数组中的项目
假设您要打印前 n 个数字，打印每个数字需要 3 次操作：
n->10，操作次数->3 x 10 = 30
n->100，操作次数->3 x 100 = 300
n->1000，操作次数->3 x 1000 = 3000
n ->10000，我们也可以说，n = 100^2（比如 k^2），
操作次数 --> 3 x 10000 = 30,000
即使 n 是某物的指数（在本例中为 100），我们的操作次数完全取决于输入的数字（n 为 10,000）。
所以我们可以说，它是线性时间复杂度算法。
每当看到“线性”一词时，您应该问 - 线性 在什么方面？通常，当我们谈论算法的运行时间是“线性时间”时，我们的意思是“算法的运行时间是 O(n)，其中 n 是输入的大小。”
你问的是如果 n = 2k 并且我们将 exponentially-sized 输入传递给函数会发生什么。在这种情况下，由于运行时间为 O(n) 且 n = 2k，因此总运行时间将为 O(2k)。这个陈述与算法以线性时间运行的事实之间没有矛盾，因为“线性时间”意味着“线性作为输入大小的函数”。
请注意，我明确选择在表达式 2k 中使用不同的变量 k 以引起注意，这里确实有两个不同的量 - 大小输入作为 k 的函数（即 2k），变量 n 更一般地表示函数输入的大小。您有时会看到这种组合，如“如果算法的运行时间为 O(n)，则 运行 大小为 2n 的输入的算法需要时间 O( 2n)。”该陈述是正确的，但解析起来有点棘手，因为 n 在那里扮演两个不同的角色。
讲师说算法的复杂度通常是根据其输入大小来衡量的。
所以，当我们说一个算法是线性的，那么即使你给它一个 2^n 的输入大小（假设 2^n 是二叉树中的节点数），该算法仍然是线性的输入大小？
以上好像是导师的意思，但我脑子里转不过来。如果你给它一个 2^n 输入，它是某个参数“n”的指数，然后称这个输入为“x”，那么，当然，你的算法对 x 是线性的。但在内心深处，它不仍然是“n”的指数吗？说它对 x 是线性的有什么意义？
如果算法具有线性time-complexity，则无论输入大小如何，它都是线性的。无论是固定大小的输入，二次还是指数。
显然 运行 固定大小数组、二次或指数的算法将花费不同的时间，但复杂度仍然是 O(n)。
也许这个例子会帮助你理解，运行 merge-sort 在大小为 16 的数组上意味着 merge-sort 是 O(1) 因为它需要不断的操作来排序大批？答案是否定的。
当我们说算法是 O(n) 时，意味着如果输入大小是 n，它与输入大小成线性关系。因此，如果 n 是另一个参数 k 的指数（例如 n = 2^k），则该算法对于输入大小也是线性的。
另一个例子是对大小为 n 的输入数组进行二进制搜索的时间复杂度。我们说对大小为 n 的排序数组的二进制搜索在 O(log(n)) 中。这意味着关于输入大小，它最多需要渐近 log(n) 比较来搜索大小为 n、
假设您要打印前 n 个数字，打印每个数字需要 3 次操作：
n->10，操作次数->3 x 10 = 30
n->100，操作次数->3 x 100 = 300
n->1000，操作次数->3 x 1000 = 3000
n ->10000，我们也可以说，n = 100^2（比如 k^2）， 操作次数 --> 3 x 10000 = 30,000 即使 n 是某物的指数（在本例中为 100），我们的操作次数完全取决于输入的数字（n 为 10,000）。
所以我们可以说，它是线性时间复杂度算法。
每当看到“线性”一词时，您应该问 - 线性 在什么方面？通常，当我们谈论算法的运行时间是“线性时间”时，我们的意思是“算法的运行时间是 O(n)，其中 n 是输入的大小。”
你问的是如果 n = 2k 并且我们将 exponentially-sized 输入传递给函数会发生什么。在这种情况下，由于运行时间为 O(n) 且 n = 2k，因此总运行时间将为 O(2k)。这个陈述与算法以线性时间运行的事实之间没有矛盾，因为“线性时间”意味着“线性作为输入大小的函数”。
请注意，我明确选择在表达式 2k 中使用不同的变量 k 以引起注意，这里确实有两个不同的量 - 大小输入作为 k 的函数（即 2k），变量 n 更一般地表示函数输入的大小。您有时会看到这种组合，如“如果算法的运行时间为 O(n)，则 运行 大小为 2n 的输入的算法需要时间 O( 2n)。”该陈述是正确的，但解析起来有点棘手，因为 n 在那里扮演两个不同的角色。