leetcode 181 Employees Earning More Than Their Managers 不会分析的数据库复杂度

https://leetcode.com/problems/employees-earning-more-than-their-managers/description/

老师上课没分析这些的复杂度，我大概认为子查询要O（n^2）

一开始，直接用了子查询，2400ms....

# Write your MySQL query statement below

select T.name as Employee

from Employee as T

where T.Salary > (select Employee.salary from Employee where Employee.Id = T.ManagerId);

然后

标程有一个2000ms的，但我也认为他复杂度需要O（n^2）

SELECT

    a.Name AS 'Employee'

FROM

    Employee AS a,

    Employee AS b

WHERE

    a.ManagerId = b.Id

        AND a.Salary > b.Salary

;

最后一个用了join，确实理论上会比较快一丢丢，但是总体来说我感觉还是O（n^2）啊，1800ms快了很多很多

SELECT

    a.Name AS 'Employee'

From

    Employee as a join Employee as b

    on a.ManagerId = b.Id

where

    a.Salary > b.Salary

;

巴特西

leetcode 181 Employees Earning More Than Their Managers 不会分析的数据库复杂度

最新文章

热门文章