第一码的复杂度是O(n)，第二码的复杂度是O(n ^2)吗？

Question

第一个代码。

def Maximum__profit_more_efficient(list):
    """compute the maximum_profit of specific stock"""

    selling_date = 0
    buying_date =  0        

    for i in range(len(list)):            
        if list[i] > list[selling_date]:
            selling_date = i                                

    for j in range(len(list)):            
        if list[j] < list[buying_date] and j <= selling_date:                
            buying_date = j            
        elif  j > selling_date:
            break           

    print(list[selling_date] -  list[buying_date])

---

第二段代码：

def brute_force(list):  
    """compute the maximum_profit of specific stock, but with higher complexity"""

    selling_date = 0
    buying_date =  0

    i = 0
    j = 0
    exit = False

    while exit == False:
        if list[i] > list[selling_date]:
            selling_date = i            

        if  i < len(list):
            i = i + 1                

        if i == len(list):                
            while j < len(list):
                if list[j] < list[buying_date] and j <= selling_date:
                    buying_date = j                    
                j = j + 1
                if j == len(list):
                    exit = True

    print(list[selling_date] -  list[buying_date])

Answer 1

第一个代码的复杂度是O(n)，你已经猜到了，但是第二个代码的复杂度也是O(n)。尽管第二段代码中有一个嵌套循环，但由于j的值只在循环外设置一次为0，所以时间复杂度只有O(n)。