algorithm - Big O 符号的数学逼近与编程中的实用数学逼近有什么关系

Question

我有一个关于渐近复杂性的问题，特别是大 O 表示法。

从数学上讲：我们有一个函数 T(n) 它的输出：我们的算法所花费的时间。

例如 T(n) = 1000 + 10n 。我们选择一个简单的函数 F(n) = n ，对于一些大的自然数 N 和常数 C ， T(n) <= CF(n) 相当于 T(n) 属于 O(f(n)) （其中 T 由 CF(n) 控制的一组函数）。

我的具体问题：我没有得到 upper bounds 的点，从特定的输入 N ，所有 T(n) 点都以 F(n) 点为上限。

数学近似与计算机科学中最坏情况复杂性和大 O 表示法之间的关系是什么

标签： algorithmtime-complexitybig-ocomplexity-theoryspace-complexity

Answer 1

在阅读有关该主题的更多信息后。这个数学证明只是一个近似值，用于解释我们的函数 T(n) [它是我们的算法执行某些特定工作所花费的指令或步骤的输出数量] 的上限为等效函数 CF(n)，其中 C 是一些特定的大常数 > 0 。所以我们的上限指的是最坏情况下的复杂度，我们的算法可以达到（并且可以达到，因为在数学上 T(n) 和 F(n) 相交于某个特定的大 N > 0 成为上界（上限属于我们的功能） ） 。所以在简历中，它是证明最坏情况复杂度是我们的算法可以达到的上限（或上界）的近似值。