时间戳

首页 > 解决方案 > 所有 O(n) 算法也是 O(n²) 吗？

algorithm - 所有 O(n) 算法也是 O(n²) 吗？

问题描述

大 O 表示法的正式定义是，如果我们有一个函数f(n)（用于算法的时间和空间）和另一个函数，并且对于所有g(x)都有常数c等no，那么。但是使用这个定义以及不断增长的二次函数总是会在某个点超过线性函数的事实，是否所有函数也是？或者更好的说法，是？c*g(n) > f(x)n > nof(n) = O(g(n))O(n)O(n²)n = O(n²)

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

解决方案

是的，所有 O(n) 算法也是 O(n²)。当谈到 Big-O 时，人们对符号非常草率。为了清楚起见，我认为最好将 O(f) 概念化为返回一组函数。使用集合表示法：

n ∈ O(n) ⊂ O(n²)

推荐阅读