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

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

complexity-theory big-o time-complexity

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

假设我们有以下复杂性:

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 回复 | 直到 6 年前

HackerBoss 6 年前

是的,你可以。

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都是正的,当它们变大时观察它们的行为。

推荐文章

Suhail Gupta · 在排序阵列中查找目标范围的时间复杂度-此解在最坏情况下是否为O(N)?

2 年前

Liana78 · 查找和最小化合并排序算法运行时分析

6 年前

Lamaman · 素数算法的复杂度是多少?

6 年前

irish Senthil · 声明变量是否对大O表示法有效?

6 年前

shir k · 大阵列中1的θ

6 年前

Monk · 为什么大Oh不总是算法的最坏情况分析?

6 年前

Faisal Alzahrani · 用Java计算程序的Big-O

6 年前

Dazcii · 如何找到3个嵌套循环的复杂性

6 年前

svaerth · 使用巨型哈希表在多项式时间内求解数独

6 年前

shinwari_afg · 使用大Oh分析while(key<=N*N)循环的复杂性

6 年前