Data Structure/ Ch02:AlgorithmAnalysis

📚 The Start of Recording TIL Summer ‘24 : Why Did I Start This Project? 🚀

🔔 Don't Miss: Continous Records of TIL '25 (Still On-Going!) 🌟

✨ A New Chapter in TIL '25: Reflecting, Growing, and Moving Forward 📖

TIL: CH02. Algorithm Anlaysis

Algorithm Analysis based on the time summation

# Listing 2.3 : Timing the Summation

import time

def sumOfN2(n):
    start = time.time()
    
    theSum = 0
    for i in range(1,n+1):
        theSum = theSum + i
        
    end = time.time()
    
    return theSum, end-start

When trying to charcterize an algorithm’s effciency, it is important to quantify the number of operations or steps that the algorithm will require. The order of magnitude function describes the size of problems, often called “Big-O notation” (for order). It provides a useful approximation to the a actual number of steps in the computation.

The Big O Notation

$f(n)$	Name
$1$	Constant
$log n$	Logarithmic
$n$	Linear
$n log n$	Log Linear
$n_{2}$	Quadratic
$n_{3}$	Cubic
$2_{n}$	Exponential

%%html
<style>
table {float:left}
</style>

Anagram Solution with various types

# Listing 2.6 Anagram Solution Checking Off

def anagramSolution1(s1, s2):
    alist = list(s2)
    
    pos1 = 0
    stillOk = True
    
    while pos1 < len(s1) and stillOk:
        pos2 = 0
        found = False
        while pos2 < len(alist) and not found:
            if s1[pos1] == alist[pos2]:    #  checks if the character at the current position pos1 in s1 is equal to the character at the current position pos2 in alist.
                found = True
            else:
                pos2 = pos2 + 1    # If the characters don't match, it increments pos2 to check the next character in alist.
        
        if found:
            alist[pos2] = None
        else:
            stillOk = False
            
        pos1 = pos1 + 1
        
    return stillOk

# testing code
anagramSolution1("apple", "pllea")    # Output : False

False

# Listing 2.7 Sort and Compare

def anagramSolution2(s1,s2):
    alist1 = list(s1)
    alist2 = list(s2)
    
    alist1.sort()
    alist2.sort()
    
    pos = 0
    matches = True
    
    while pos < len(s1) and matches:
        if alist1[pos] == alist2[pos]:
            pos = pos + 1
        else:
            matches = False
            
    return matches   

# Listing 2.8 Count and Compare

def anagramSolution4(s1, s2):
    c1 = [0]*26
    c2 = [0]*26
    
    for i in range(len(s1)):
        pos = ord(s1[i])-ord('a')
        c1[pos] = c1[pos] + 1
        
    for i in range(len(s2)):
        pos = ord(s2[i])-ord('a')
        c2[pos] = c2[pos] + 1
        
    
    j = 0
    stillOK = True
    while j<26 and stillOK:
        if c1[j]==c2[j]:
            j = j + 1
        else:
            stillOK = False
            
    return stillOK