时间复杂度 - 这两种算法之间哪个更快？

Question

描述

此程序的目标是从用户订单和这些订单的productList foreach填充orderList.(请忽略此伪C#代码可能出现的语法错误)

数据结构

class User {
    List<Order> orders; 
}

class Order {
    List<Product> products;
}

class Product {
    int price;
}

List<User> userList = GetUsersFromDB();

List<Order> orderList     = new List<Order>();  
List<Product> productList = new List<Product>();

第一版

foreach(User u in userList) {
    foreach(Order o in u.orders) {
        orderList.Add(o);
        foreach(Product p in o.products) {
            productList.Add(p);
        }
    }
}

第二版

foreach(User u in userList) {
    foreach(Order o in u.orders) {
        orderList.Add(o);
    }
}

foreach(Order o in orderList) {
    foreach(Product p in o.products) {
        productList.Add(p);
    }
}

我的想法

• 第一个程序T(n)= O(n ^ 3)
• 第二个程序T(n)= O(n ^ 2)+ O(n ^ 2)<O(n ^ 3)

因此第二个程序更快,更正确？

Answer 1

概观

你对第二种情况的分析是错误的.由于第一个循环的每个内部事物的orderlist中都有一个条目,因此foreach(Order o in orderList)循环遍历n ^ 2个项目.说过这里有一个免责声明,因为它代表了很多东西,所以n在这里不是很有意义.

更好的方法是使用u,o和p来查看它.

情况1

第一个显然是O(uop).

案例2

这种情况有两组循环.第一对循环O(uo)正如您所期望的那样.

然后第二对循环以uo项目循环开始,然后是O(p)的内循环,所以第二对循环开始O(uop).总的来说,这使得O(uo)+O(uop)这相当于O(uop),同为1的情况下.

基本上第二种情况只是稍微移动一下,它实际上根本没有改变基本算法.

真实世界

一如既往,如果您实际关注的是真实世界的性能,而不仅仅是理论上的算法复杂性(在查看特定情况时并不总是有用),那么就可以对两种技术的性能进行基准测试.