计数的时间复杂度是多少？
What is the time complexity of counting?
我有 n 本书的清单，例如 books = ["1984", "Harry Potter", "Hamlet"]。
此外，我有一个列表列表，其中每个内部列表代表读过一些书的人（可能是全部或none），可能 0 或多次，所以，例如，我可以有类似 readings = [["1984", "Harry Potter", "Harry Potter"], ["Hamlet", "Harry Potter"], [], ["Hamlet", "Hamlet", "Hamlet", "Hamlet"]].
的东西
对于readings我需要计算每本书被阅读了多少次。就编码而言，这似乎是一个微不足道的操作（创建 title : number of readings 的字典，遍历每个内部列表并增加键值对中的值），但我很难理解该计数的复杂性。
idea №1：由于有n本书，时间复杂度为O(n)
想法№2：由于n本书和m个人readings，时间复杂度为O(nm)
idea №3: 由于每本书的阅读次数都是有限的，例如n次，n^2次甚至n^n次，我不知道时间复杂度是多少，因为我不知道这里应该选择n的最大幂是多少，看起来是无穷大。
那么统计所有书被读了多少遍的时间复杂度是多少？
您建议的字典方法听起来不错。如果我们可以假设字典访问是一个恒定时间的操作，那么列表中的书籍数量 (n) 将是无关紧要的。
您描述的算法的时间复杂度为 O(k)，其中 k 是所有读数的总大小。如果您想象遍历所有阅读中的所有书籍并为它们更新字典，这很容易看出。
无论您还知道什么，这都是事实。如果没有关于此列表大小的更多信息，您将无法获得更精确的算法时间复杂度表达式。
但是，如果你知道的更多，你可以用更有用的方式来表达。例如：
- 如果人均阅读数是r。那么，复杂度就是O(rm)，其中m是
readings. 的人数
- 一个人可以阅读同一本书的次数是有上限的。如果该值是有界的，则可以将其视为常量。然后，你的复杂度是 O(nm)，就像你建议的那样。 （这个界限不太可能取决于 n。）
好像你理解了时间复杂度的概念，只是不知道你是如何allowed/expected表达它的。
我有 n 本书的清单，例如 books = ["1984", "Harry Potter", "Hamlet"]。
此外，我有一个列表列表，其中每个内部列表代表读过一些书的人（可能是全部或none），可能 0 或多次，所以，例如，我可以有类似 readings = [["1984", "Harry Potter", "Harry Potter"], ["Hamlet", "Harry Potter"], [], ["Hamlet", "Hamlet", "Hamlet", "Hamlet"]].
对于readings我需要计算每本书被阅读了多少次。就编码而言，这似乎是一个微不足道的操作（创建 title : number of readings 的字典，遍历每个内部列表并增加键值对中的值），但我很难理解该计数的复杂性。
idea №1：由于有n本书，时间复杂度为O(n)
想法№2：由于n本书和m个人readings，时间复杂度为O(nm)
idea №3: 由于每本书的阅读次数都是有限的，例如n次，n^2次甚至n^n次，我不知道时间复杂度是多少，因为我不知道这里应该选择n的最大幂是多少，看起来是无穷大。
那么统计所有书被读了多少遍的时间复杂度是多少？
您建议的字典方法听起来不错。如果我们可以假设字典访问是一个恒定时间的操作，那么列表中的书籍数量 (n) 将是无关紧要的。
您描述的算法的时间复杂度为 O(k)，其中 k 是所有读数的总大小。如果您想象遍历所有阅读中的所有书籍并为它们更新字典，这很容易看出。
无论您还知道什么，这都是事实。如果没有关于此列表大小的更多信息，您将无法获得更精确的算法时间复杂度表达式。
但是，如果你知道的更多，你可以用更有用的方式来表达。例如：
- 如果人均阅读数是r。那么，复杂度就是O(rm)，其中m是
readings. 的人数
- 一个人可以阅读同一本书的次数是有上限的。如果该值是有界的，则可以将其视为常量。然后，你的复杂度是 O(nm)，就像你建议的那样。 （这个界限不太可能取决于 n。）
好像你理解了时间复杂度的概念，只是不知道你是如何allowed/expected表达它的。