代码之家 › 专栏 › 技术社区 › DaveDev

大O与N+1有什么关系?

big-o theory orm

DaveDev · 技术社区 · 14 年前

大0尝试回答算法复杂性中的效率低下问题。n+1描述了效率低下,因为它与数据库查询相关,是通过单独的查询来填充集合中的每个项。

我目前正试图在不同的工作环境中理解每一个概念,现在我想知道是否有人能解释这两个概念是否以任何方式相互关联?有人能描述一下这两种情况吗?

1 回复 | 直到 14 年前

Gabriel Å Äerbák 14 年前

复杂度的大O符号是使用图灵机的操作数定义的,因此可以描述任何算法。n+1选择问题描述了效率低下的关系算法(查询),它总是需要对每条记录执行n+1操作。由于该查询是一种算法,所以您可以分析其复杂性。

O(n+1)=O(n)

这意味着你有线性复杂性。现在,如果我们使用正确的算法,那么对于两个表中的每一个,每个记录只需要一个操作(选择)。复杂性将是:

O(2)=O(1)

该算法具有恒定的复杂性。这表明,通过分析这两种算法的复杂性,您将看到哪个算法受到n+1选择问题的影响。

这清楚吗?

推荐文章

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

2 年前

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

6 年前

Kodean · Java:循环字符串长度时间复杂性

6 年前

screeb · 依赖于收敛的算法的大O

6 年前

f1sh3r0 · 从图中确定渐近增长率

6 年前

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

6 年前

alekscooper1 · 这里是f(x)=O(g(x))还是反之亦然?

6 年前

user3487554 · 时间复杂性组合

6 年前

user6217340 · 大O复杂性

6 年前

Jawwad Rafiq · 对两个相关循环的复杂性感到困惑?

6 年前