我有一个程序，它从一个数组列表中获取数据，需要花费o（n）个时间。但也有一个嵌套for循环，它需要o（n^2）时间。程序的时间复杂度是o（n^2）还是o（n^3）？
esbemjvw1#
这取决于这两部分如何相互作用。如果它们互相调用（例如，对于列表中的每个元素（o（n）），则执行一个方法，在整个列表（o（n2））上执行嵌套循环，然后将它们相乘，得到o（n3）的时间复杂度。如果它们是以串行方式调用的-即，您遍历列表（o（n）），并且一旦您是一个执行o（n2）算法的人，反之亦然，那么o（n）部分与o（n2）部分相比可以忽略不计，并且总体时间复杂度是o（n2）。
1条答案
按热度按时间esbemjvw1#
这取决于这两部分如何相互作用。如果它们互相调用（例如，对于列表中的每个元素（o（n）），则执行一个方法，在整个列表（o（n2））上执行嵌套循环，然后将它们相乘，得到o（n3）的时间复杂度。
如果它们是以串行方式调用的-即，您遍历列表（o（n）），并且一旦您是一个执行o（n2）算法的人，反之亦然，那么o（n）部分与o（n2）部分相比可以忽略不计，并且总体时间复杂度是o（n2）。