HW3 開發紀錄
 

Q2

 
Iterative 
char smallest_character(char str[],char c)
{
    int l =0, r = strlen(str)-1;
    char res = str[0];
    while(l <=r ) {
        int m = l + (r-l)/2;
        if (str[m]>c) {
            res = str[m];
            r = m-1;
        } else
            l = m+1;
    }
    return res;
}
由於題目給的數列是sorted,所以採用二分法可以讓原本搜尋時間複雜度可以從O(n) => O(logn)
透過改變左右邊界的方式調整每次比較的位置,可以省去多餘的比較時間
舉第一個範例為例 最後 return c
 
Recursive
char smallest_character(char str[],char c)
{
    char temp;
    if(strlen(str)==0)
        return 0;
    else if(str[0]>c)
        return str[0];
    else {
        temp = smallest_character(str+1,c);
        if(temp<c)
            return str[0];
        else
            return temp;
    }
    return 0;
 
}
 
  • Recursive 版本就是從一個跑到最後一個只要一比 c 大就回傳,,所以worst case 就是跑完整格array 時間複雜度為O(n)
 

舉題目第二題為例:

implementation time