代码之家 › 专栏 › 技术社区 › No Name QA

二元函数复杂性的大o简化

complexity-theory big-o time-complexity

No Name QA · 技术社区 · 7 年前

假设我们有以下复杂性:

T(n, k) = n^2 + n + k^2 + 15*k + 123

我们不知道 n 和 k .

我可以说,在很大的复杂性方面,将是:

T(n) = O(n^2 + n + k^2 + 15*k)

我能再简单一点吗? 15 不变的,否则我可以放弃 n 和 15*k ?

更新:根据这个 link 大O不是两个或多个变量的有效表示法

1 回复 | 直到 7 年前

HackerBoss 7 年前

是的,你可以。

O(n^2+n+k^2+15*k)=O(n^2+n)+O(k^2+15*k)=O(n^2)+O(k^2)=O(n^2+k^2)

这确实假设k和n都是正的,当它们变大时观察它们的行为。

推荐文章

Matthew · 发现程序的时间复杂性

2 年前

TreasureGhost · 以下函数的时间复杂度是多少

2 年前

Abdullah Kassar · std::upper_bound()是线性的吗?c++

2 年前

user129393192 · 这个问题的最优算法是什么?

2 年前

3366784 · 使用序列初始化字符串的时间复杂度是多少?

3 年前

nehacharya · 这个代码的时间复杂度是O(n^2)还是O(nlogn)?

3 年前

control plane · ruby中链表上size调用的时间复杂性

3 年前

learner · 查找最长的子字符串

3 年前

hackrack · 在javascript中,如何返回时间复杂度为O(n)的相同字母元素?

8 年前

data-oil · 在字符串列表中搜索的高效快捷方法

8 年前