samedi 19 septembre 2020

why is there an anomaly in asymptotic time and actual time for each solution?

I was solving this problem:- You're given strings J representing the types of stones that are jewels, and S representing the stones you have. Each character in S is a type of stone you have. You want to know how many of the stones you have are also jewels.

The letters in J are guaranteed distinct, and all characters in J and S are letters. Letters are case sensitive, so "a" is considered a different type of stone from "A".

Example 1:

Input: J = "aA", S = "aAAbbbb" Output: 3 Example 2:

Input: J = "z", S = "ZZ" Output: 0

My logic for solution 1.
Hash the stones(unordered_map) so that we have the frequency of each type and have to find only the different stones in the given jewels once. The find function takes o(n) for each stone n hence the time complexity is O(n^2).

int numJewelsInStones(string j, string s) {
        
        unordered_map<char, int>stones;
        for(char s1:s)
            ++stones[s1];
       
        auto it = stones.begin(); 
        int count = 0;
        for(it = stones.begin(); it != stones.end(); ++it)
        {
            char s1 = it->first;
            if(j.find(s1) != string::npos)
                count += it->second;
            
        }
        return count;

So i thought that o(n^2) was too much and decided to try to furthur optimise this. So i hashed the jewels as well by putting it into an unordered_set. That way, all duplicated are removed and it takes o(1) time to find a stone in it. So, for each stone it takes o(1) time and hence time complexity becomes o(n).

int numJewelsInStones(string j, string s) {
        
        unordered_map<char, int>stones;
        for(char s1:s)
            ++stones[s1];
        unordered_set<char>uset(j.begin(), j.end()); 
        auto it = stones.begin(); 
        int count = 0;
        for(it = stones.begin(); it != stones.end(); ++it)
        {
            char s1 = it->first;
            
            if(uset.find(s1) != uset.end())
                count += it->second;
                
        }
        return count;

The problem arises here- when i used the clock function from time.h to measure the run time
for solution 1 i got 0.000126 units of time
for solution 2 i got 0.000145 units of time
which does not makes sense when the first one is o(n^2) and the second one is o(n).
btw, this is my code for getting the time-

int main()
{
    clock_t tStart = clock();
    Solution ob;
    string j = "aA", s = "aAAbbbb";
    cout << ob.numJewelsInStones(j, s) << endl;
    cout << (double)(clock() - tStart)/CLOCKS_PER_SEC;
    cout << endl;
    return 0;
}

Is anyone able to explain this anomaly to me?

Aucun commentaire:

Enregistrer un commentaire