<jupyter_start><jupyter_text>chapter 9 and 10定義はテキストから引っ張った。- bese-case running time: 入力がアルゴリズムにとって最も好ましい場合の計算時間- worst-case running time: あるサイズのすべての入力に対して計算時間の最大値を取ったもの- average-case running time; あるサイズのすべての入力に対して計算時間の平均を取ったものworst-case running time: upper bound of computation time   asymptotic notationIntroducing the definition of asymptotic notation is useful to discuss the relationship between computation time and input size.- Big O notationBig O notation provides the upper bound of rate of growth.Example.\begin{equation*}g(x) \in \mathcal{O}(x^2)\end{equation*}This means rate of $g(x)$'s growth is not faster than that of $x^2$.How do we check this?- If computation time is represented by sum of some terms, pick only the maximum term.- If maximum terms are product, remove constant coefficient. https://qiita.com/drken/items/872ebc3a2b5caaa4a0d0が計算量の話でよくまとまっている Some important class of computational complexity.Let n be the size of input.- $O(1)$ :constant running time- $O(\log n)$: logarithmic running time- $O(n)$: linear running time- $O(n \log n)$: log-linear running time- $O(n^k)$: polynomial running time- $O(c^n)$: exponential running time  Chapter 10Using some example algorithm, we try to understand the computational complexity. Search Algorithm<jupyter_code>def search(L,e):
    """
    This function check whether a list includes some element. 
    If yes, return True, else return False.
    
    Arguments:
    L: list
    e: some object
    
    """
    
    for i in range(len(L)):
        if L[i]== e:
            return True
        return False<jupyter_output><empty_output><jupyter_text>If lists are sorted, we can use binary search algorithm. This algorithm reduces worst-case running time.<jupyter_code>def bsearch(L,e):
    """
    This function check whether a list includes some element using binary search algorithm.
    If yes, return True, else return False.
    
    Arguments:
    L: list that is sorted
    e: some object
    
    """
    
    def bSearch(L,e,low,high):
        
        if high==low:
            return L[low]==e
        
        mid = (low+high)//2
        
        if L[mid] == e:
            return True
        
        elif L[mid] > e:
            if low == mid:
                # there is no search space
                return False
            
            else:
                return bSearch(L,e,low,mid-1)
            
        else:
            return bSearch(L,e,mid+1,high)
        
        
    if len(L) == 0:
        return False
    else:
        return bSearch(L,e,0,len(L)-1)<jupyter_output><empty_output><jupyter_text>Sorting algorithmPreviously, we can reduce computational time if a list is sorted. Should we sort the list and then search some data? How much time do we need to sort the list ?Basically, we must read each element of list. Thus if we need to search element in the list for a lot of time, it may be efficient to sort the list first.Through examples, consider these things.<jupyter_code>def selSort(L):
    """
    Sort list by ascending order.
    
    Argument:
    
    L: list but can be compared using >
    
    """
    
    suffixStart = 0 # prefix,リストのうち最初からi番目までの要素からなる部分リスト suffix はcomplement.
    
    while suffixStart != len(L): #O(len(L))
        for i in range(suffixStart,len(L)):#O(len(L))
            if L[i] < L[suffixStart]:
                L[suffixStart], L[i] = L[i], L[suffixStart]
                
        suffixStart += 1<jupyter_output><empty_output><jupyter_text>This selection sort is not efficient since computational time is $O(len(L)^2)$.However, divide-and-conque algorithm can improve previous one.<jupyter_code>def merge(left, right, compare):
    """
    Return new sorted list according to compare function
    
    Arguments:
    left: sorted list
    right: sorted list
    compare: lambda function
    """
    
    result = []
    i,j =0,0
    
    # for the case that elements remain in both lists.
    while i < len(left)  and j < len(right):
        if compare(left[i],right[j]):
            result.append(left[i])
            i += 1
        else:
            result.append(right[j])
            j += 1
            
    # Here after consider the case that elements remain in only one list
    while i < len(left):
        result.append(left[i])
        i += 1
            
    while j < len(right):
        result.append(right[j])
        j += 1
    
    return result  
def mergeSort(L, compare = lambda x, y: x < y):
    """
    this function returns new sorted list that contains same elements in the original one.
    
    Arguments:
    L :list
    
    """
    
    if len(L)<2:
        return L[:]
    
    else:
        middle = len(L)//2
        # divides list
        left = mergeSort(L[:middle],compare) #ここでリストをどんどん分割してく
        right = mergeSort(L[middle:],compare)
    return merge(left, right, compare)
L = [2,1,4,5,3]
print(mergeSort(L), mergeSort(L,lambda x,y: x>y))<jupyter_output>[1, 2, 3, 4, 5] [5, 4, 3, 2, 1]
{'fraction_non_alphanumeric': 0.09573612228479485, 'fraction_numerical': 0.009855189058728881, 'mean_word_length': 2.5070521861777153, 'pattern_counts': {'":': 0, '<': 23, '<?xml version=': 0, '>': 19, 'https://': 1, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 0, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
{'chain_length': '4', 'dir': 'jupyter-structured-clean-dedup', 'id': '629705', 'license': 'MIT', 'n_tokens_mistral': 1625, 'n_tokens_neox': 1560, 'n_words': 520, 'path': 'chap9-10.ipynb', 'repo_name': 'tokupooh/prog_intro', 'size': '4972'}