Big O 与 N+1 有何关系?

Dav*_*Dev 3 theory big-o orm

Big 0 试图回答算法复杂性低效的问题。N+1 描述了效率低下,因为它与数据库查询相关,需要单独查询以填充集合中的每个项目。

我目前正试图在不同的工作环境中了解这些概念中的每一个,现在我想知道是否有人可以解释这两个概念是否以任何方式相互关联?有人可以提供适用于他们两个的描述吗?

Gab*_*bák 5

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

O(N+1)=O(N)

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

O(2)=O(1)

该算法具有恒定的复杂性。这表明,通过分析两种算法的复杂性,您会看到哪一种会遇到 N+1 选择问题。

这清楚吗?