開發紀錄
Homework#3
 

Question 2

由題目給定之條件 : input : a sorted character array 可知其為一已"排序"的array, 所以
  • Iterative
char smallest_character(char str[], char c){       
        int i;
        for (i=0 ; i < strlen(str) ; i++) {
                if (str[i] > c)
                        return str[i];
        }
        return str[0];
}
str[] : 已排序陣列  ,  c : the reference character
 
Time complexity : O(n)
 
  • Recursive
char smallest_character(char str[], char c, int i){
        if (i == strlen(str))
                return str[0];   // 終止條件1: 搜尋str[]完畢, ref. chracter為最大值, 傳回str[0] 其為最小值
        else if (str[i] > c)
  •           return str[i];    // 終止條件2: 找到大於 ref. chracter的值, 傳回str[i] 
        else
                return smallest_character(str, c, ++i);                
}
str[] : 已排序陣列  ,  c : the reference character , i : 初始條件值(傳入值會為0)
 
Time complexity : O(n)
 
  • 效能分析
因為都是 O(n) 的等級, 跑起來 不分伯仲
 
Performance counter stats for './recursive' (5 runs):
             3,534      cache-misses              #   13.174 % of all cache refs      ( +- 32.48% )
            26,823      cache-references                                              ( +-  1.80% )
           448,208      instructions              #    0.78  insns per cycle          ( +-  0.78% )
           574,044      cycles                     ( +-  2.50% )
  0.000546109 seconds time elapsed                                          ( +-  8.96% )
Performance counter stats for './iterative' (5 runs):
 
             3,136      cache-misses              #   12.182 % of all cache refs      ( +- 28.55% )
            25,745      cache-references                                              ( +-  0.97% )
           444,324      instructions              #    0.84  insns per cycle          ( +-  0.46% )
           529,628      cycles                     ( +-  2.58% )
0.000528997 seconds time elapsed                                          ( +- 10.35% )
 

Question 4