c - 经验 运行-时间分析
c - empirical run-time analysis
嘿，所以我很难掌握实证 运行 时间分析。所以我有这个问题：
假设我们有一个 O(1) 函数，执行时间为 8 秒，n = 2,000。如果 n = 10,000，您期望 运行 时间是多少？
现在这是我认为错误的思考过程：
如果 T(n) 是 O(1) 那么 T(n) = c * O(1) 其中 c 只是某个常数。所以求解 c 我们得到 c = T(n) / O(1)。现在，因为我们知道 T(2000) = 8s 和 n = 2000，我们可以将其插入以求解 c，c = (8s) / (2000) 得到 0.004。
现在我们必须对 n = 10,000 做同样的事情，所以在这种情况下 T(10,000)= c * O(1)
在这种情况下，我们可以只插入我们之前发现的相同的 c，因为它只是一个常数，并为 O(1) 插入 10,000，这将得到 T(10,000) = (0.004) * 10,000，等于 40s。我只是不确定我的思考过程是否正确。
正确答案是我们不能期待任何特定时间。
说一个函数的 运行 时间 O(1) 就是说有一些数字 C 使得函数总是 运行s 在少于 C 秒。如果函数 运行 在 8 s 一次，我们知道 C 至少是 8。但它可能是一百万。或 septillion。
O(1) 告诉我们的是，无论 n 是多少，运行 时间都是有限的。 运行时间可以随着n的不同而上下变化，但总是受C的限制。
相比之下，将其与具有 运行 时间 O(n) 的函数进行比较。这意味着有一个数字 C 使得函数的 运行-time 总是小于 C*n 秒（除了允许有限数量的例外）。所以我们没有固定的限制；我们有一个取决于 n 的限制。随着 n 的增长，此函数 可能 需要越来越多的时间。
也可能不会。 O 表示法仅告诉您函数的 运行 时间限制。它不会告诉您实际的 运行 时间。如果我知道你昨天在你的车里加了一加仑汽油，你走了 30 英里，我知道你的车每加仑至少可以跑 30 英里。如果你今天加两加仑汽油，我知道你至少可以跑 60 英里，但也许你可以跑更多，但我不知道你实际能跑多远。我知道你的旅行有限制，但我不知道它到底是什么，也不知道你能走多远。
big-O 符号的问题通常是非正式的（更不用说草率的）符号，它带有很多假设。
首先，O 符号1 期望其括号之间有一个函数，所以像 O(1) 这样的符号一开始并不清楚（因为 1 是一个数字）。
在某些数学领域习惯用“1”表示函数 f:ℕ→ℕ 定义为 f(n) = 1 ∀ n ℕ.
这只是一个为每个输入2.
返回1的函数
要考虑的另一点是，经典定义的 O 对单变量函数进行运算，为避免歧义，应始终显式写入两个函数的自变量。
然而，通常不会这样做，因为从上下文中可以清楚地看出我们只处理一种特定的函数。
为了 reader 的警觉性，并以繁琐的符号为代价，我不会删除自变量，因此将 O(1) 写为 O(1(n)).
最后，相对于使用等号。
我们希望通过符号 f(n) ∊ O(1(n)) 阐明 O(1(n)) =251=] 函数 f(n) w.r.t。另一个函数 returns 1 用于每个输入。
大 O 表示法是 shorthand（就像极限表示法一样），在我们的特定情况下转换为
f(n) ∊ O(1(n))
∃N ∊ ℕ: ∀n > N |f(n)| ≤ M · |1(n)| （根据定义）
∃N ∊ ℕ: ∀n > N |f(n)| ≤ M · 1(n) （1(n) 始终为正）
∃N ∊ ℕ: ∀n > N |f(n)| ≤ M · 1 （对于所有 n，1(n) = 1）
∃N ∊ ℕ: ∀n > N |f(n)| ≤ M
因此，符号简化为 f(n) 的绝对值受（未指定！）常量 M 限制。
这给我们留下了 很多 函数，即使给定了某个点的函数值。
例如，即使我们知道 f(2000) = 8，这两个函数 g(n) = 8 cos(n-2000)和 h(n) = 8 en-2000 都在 O(1(n) ) 但它们在 n = 10000 时的值不同！
大 O 表示法很有用，因为它 简化了 事情，但到目前为止，它似乎失败了很长时间。
缺少的部分是我们正在处理算法及其时间复杂度3 所以我们感兴趣的函数 f是：
非分段.
我们认为分段函数是由两种算法产生的，而不是单个算法的表达式。
单调非递减。
我们假设对于同一个问题，更大的实例需要更长的时间来解决。
在这个假设下，我们可以看到，如果一个函数是有界的，那么在某个点它必须停止增加并无限期地保持在该值。
这就是f(n)∊O(1(n))表示法：f 是一个常数函数（渐近）。
如果 f 是常数那么 f(n) = c 并且如果 f( 2000) = 8 然后 c = 8 因此 f(10000) = 8.
big-O 符号的最佳用法如下：取 O 括号之间的函数，将其乘以常数 c 并用它代替 f。
有时我们甚至不关心常量：O(1(n)) 意味着如果我们将 n 的输出加倍保持不变，O(n) 意味着如果我们加倍 n 输出加倍（对于 n = 2，n 为 2），O(n2) 意味着如果我们加倍 n 输出四倍 (n2 是 4 n = 2) 等等。
你的方法有两个问题：说 T(n) = c * O(1) 是正确的但没有用，我们没有取得任何进展，因为我们只是说 T(n) 是常数乘以另一个常数（记住 O(1) 是一个常数函数）因此它是一个常数。
另一个错误是将 O(1) 替换为 n 以获得 c.
的值
O(1) 是一个 set 函数，即使我们把它写成 c' （意味着所有可能的常量）这也不是 n! n是输入值，问题实例编码的大小而c'是一个任意 持续的。
这就是常数函数的全部要点：它们不依赖于输入，如果您愿意，它们在这方面是任意。
1 不是严格意义上的operator。如果我们将注意力集中在集合 C 和 C 值上定义的函数（例如 f ∊ C→C) 然后 O 映射一个 C→ C 函数到 set of C→C 函数(例如 O:(C→C)→℘(C→C)) 因此不是来自和指向同一集合的映射。
2 符号有意模糊，让数学家在不同的上下文中使用它；我们将它用于自然值序列，但它可以扩展到任何集合，并扩展到返回任何上下文隐含代数结构的 "unity" 的含义。
3请注意运行-时间是一个非常非常具有误导性的术语！
嘿，所以我很难掌握实证 运行 时间分析。所以我有这个问题：
假设我们有一个 O(1) 函数，执行时间为 8 秒，n = 2,000。如果 n = 10,000，您期望 运行 时间是多少？
现在这是我认为错误的思考过程： 如果 T(n) 是 O(1) 那么 T(n) = c * O(1) 其中 c 只是某个常数。所以求解 c 我们得到 c = T(n) / O(1)。现在，因为我们知道 T(2000) = 8s 和 n = 2000，我们可以将其插入以求解 c，c = (8s) / (2000) 得到 0.004。 现在我们必须对 n = 10,000 做同样的事情，所以在这种情况下 T(10,000)= c * O(1) 在这种情况下，我们可以只插入我们之前发现的相同的 c，因为它只是一个常数，并为 O(1) 插入 10,000，这将得到 T(10,000) = (0.004) * 10,000，等于 40s。我只是不确定我的思考过程是否正确。
正确答案是我们不能期待任何特定时间。
说一个函数的 运行 时间 O(1) 就是说有一些数字 C 使得函数总是 运行s 在少于 C 秒。如果函数 运行 在 8 s 一次，我们知道 C 至少是 8。但它可能是一百万。或 septillion。
O(1) 告诉我们的是，无论 n 是多少，运行 时间都是有限的。 运行时间可以随着n的不同而上下变化，但总是受C的限制。
相比之下，将其与具有 运行 时间 O(n) 的函数进行比较。这意味着有一个数字 C 使得函数的 运行-time 总是小于 C*n 秒（除了允许有限数量的例外）。所以我们没有固定的限制；我们有一个取决于 n 的限制。随着 n 的增长，此函数 可能 需要越来越多的时间。
也可能不会。 O 表示法仅告诉您函数的 运行 时间限制。它不会告诉您实际的 运行 时间。如果我知道你昨天在你的车里加了一加仑汽油，你走了 30 英里，我知道你的车每加仑至少可以跑 30 英里。如果你今天加两加仑汽油，我知道你至少可以跑 60 英里，但也许你可以跑更多，但我不知道你实际能跑多远。我知道你的旅行有限制，但我不知道它到底是什么，也不知道你能走多远。
big-O 符号的问题通常是非正式的（更不用说草率的）符号，它带有很多假设。
首先，O 符号1 期望其括号之间有一个函数，所以像 O(1) 这样的符号一开始并不清楚（因为 1 是一个数字）。
在某些数学领域习惯用“1”表示函数 f:ℕ→ℕ 定义为 f(n) = 1 ∀ n ℕ.
这只是一个为每个输入2.
要考虑的另一点是，经典定义的 O 对单变量函数进行运算，为避免歧义，应始终显式写入两个函数的自变量。
然而，通常不会这样做，因为从上下文中可以清楚地看出我们只处理一种特定的函数。
为了 reader 的警觉性，并以繁琐的符号为代价，我不会删除自变量，因此将 O(1) 写为 O(1(n)).
最后，相对于使用等号。
我们希望通过符号 f(n) ∊ O(1(n)) 阐明 O(1(n)) =251=] 函数 f(n) w.r.t。另一个函数 returns 1 用于每个输入。
大 O 表示法是 shorthand（就像极限表示法一样），在我们的特定情况下转换为
f(n) ∊ O(1(n))
∃N ∊ ℕ: ∀n > N |f(n)| ≤ M · |1(n)| （根据定义）
∃N ∊ ℕ: ∀n > N |f(n)| ≤ M · 1(n) （1(n) 始终为正）
∃N ∊ ℕ: ∀n > N |f(n)| ≤ M · 1 （对于所有 n，1(n) = 1）
∃N ∊ ℕ: ∀n > N |f(n)| ≤ M
因此，符号简化为 f(n) 的绝对值受（未指定！）常量 M 限制。
这给我们留下了 很多 函数，即使给定了某个点的函数值。
例如，即使我们知道 f(2000) = 8，这两个函数 g(n) = 8 cos(n-2000)和 h(n) = 8 en-2000 都在 O(1(n) ) 但它们在 n = 10000 时的值不同！
大 O 表示法很有用，因为它 简化了 事情，但到目前为止，它似乎失败了很长时间。
缺少的部分是我们正在处理算法及其时间复杂度3 所以我们感兴趣的函数 f是：
非分段.
我们认为分段函数是由两种算法产生的，而不是单个算法的表达式。单调非递减。 我们假设对于同一个问题，更大的实例需要更长的时间来解决。
在这个假设下，我们可以看到，如果一个函数是有界的，那么在某个点它必须停止增加并无限期地保持在该值。
这就是f(n)∊O(1(n))表示法：f 是一个常数函数（渐近）。
如果 f 是常数那么 f(n) = c 并且如果 f( 2000) = 8 然后 c = 8 因此 f(10000) = 8.
big-O 符号的最佳用法如下：取 O 括号之间的函数，将其乘以常数 c 并用它代替 f。
有时我们甚至不关心常量：O(1(n)) 意味着如果我们将 n 的输出加倍保持不变，O(n) 意味着如果我们加倍 n 输出加倍（对于 n = 2，n 为 2），O(n2) 意味着如果我们加倍 n 输出四倍 (n2 是 4 n = 2) 等等。
你的方法有两个问题：说 T(n) = c * O(1) 是正确的但没有用，我们没有取得任何进展，因为我们只是说 T(n) 是常数乘以另一个常数（记住 O(1) 是一个常数函数）因此它是一个常数。
另一个错误是将 O(1) 替换为 n 以获得 c.
的值
O(1) 是一个 set 函数，即使我们把它写成 c' （意味着所有可能的常量）这也不是 n! n是输入值，问题实例编码的大小而c'是一个任意 持续的。
这就是常数函数的全部要点：它们不依赖于输入，如果您愿意，它们在这方面是任意。
1 不是严格意义上的operator。如果我们将注意力集中在集合 C 和 C 值上定义的函数（例如 f ∊ C→C) 然后 O 映射一个 C→ C 函数到 set of C→C 函数(例如 O:(C→C)→℘(C→C)) 因此不是来自和指向同一集合的映射。
2 符号有意模糊，让数学家在不同的上下文中使用它；我们将它用于自然值序列，但它可以扩展到任何集合，并扩展到返回任何上下文隐含代数结构的 "unity" 的含义。
3请注意运行-时间是一个非常非常具有误导性的术语！