Why good algorithm take more time than bad algorithm?


  • 0
    C

    Using followed solution by Sort function which took 16ms although its time complexity is O(nlogn).

    class Solution {
    public:
    int longestConsecutive(vector<int> &num) {
        
        sort(num.begin(), num.end());
        int max = 1, count = 1, flag = 1;
        if(num.size() == 1)
            return 1;
            
        for(int i = 1; i < num.size(); i++){   
            if(num[i] - num[i-1] == 1){
                flag = 1;
                count++;
            }
            else if(num[i] - num[i-1] == 0 && flag){
                continue;              
            }
            else{              
                max = max>count?max:count;
                count=1;
                flag = 0;             
            }        
            max = max>count?max:count;         
        }
        return max;       
    }
    };
    

    But it hadn`t met the question require.
    Therefore, using the unordered_map to solve this problem to meet the require but it took 33ms.(code as followed)

    class Solution {
    public:
    int longestConsecutive(vector<int> &num) {
        
        unordered_map<int, bool> hashMap;
        for(int i = 0; i < num.size(); i++)
            hashMap[num[i]] = true;
            
        int longest = 0;
        
        for(int i = 0; i < num.size(); i++){           
            int length = 1;
            int left = num[i] - 1, right = num[i] + 1;
            while(hashMap[left]){                
                hashMap[left--] = false;
                length++;               
            }
            while(hashMap[right]){                
                hashMap[right++] = false;
                length++;                
            }
            longest = longest > length? longest: length;
        }
        return longest;
    }
    };
    

    Why good algorithm take more time than bad algorithm?
    Is it caused by the case scale?


  • 2
    D

    I could think of 2 main reasons

    • A high constant in front of the actual complexity
    • Not being cache friendly, for example quick sort is faster than heap sort just because is cache friendly

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.