经典算法题 ----关于效率

在网上看了几个算法题
居然发现速度最快的接法我居然看不懂。。
请高手帮我贴上上详细注释，或则为什么能这样算的原因把 谢谢 分少。
package calculation.fuxi.interstingsuanfa;
/*
 * 给定一个十进制数N，写下从1开始，到N的所有整数，然后数一下其中出现的所有"1"的个数。
例如：
N=2，写下1，2。这样只出现了1个"1"
N=12,写下 1,2,3,4,5,6,7,8,9,10,11,12。这样"1"的个数是5
请写出一个函数，返回1到N之间出现"1"的个数，比如 f(12)=5
一开始看这个就想到遍历1-N，每个数里面的1数量加起来，这样算法复杂度为 N乘N的位数，即O(NLogN)。
后来看了原作所写，这个问题有复杂度为o(LogN)的解，于是思考了一番，用递归实现了。
同时写上O(NLogN)的遍历算法和原文作者的算法以作比较 */
 interface Algrithm {
     public int resolve(int number);
 }
 
class RecursiveAlgrithm implements Algrithm {// 按位递归算法,o(LogN)
      @Override
     public int resolve(int number) {
         if (number == 0) {
             return 0;
          }
        int length = (int) Math.log10(number);
         if (length == 0) {
             return 1;
          } else {
             int currentLvl = scale(10, length);
             int head = number / currentLvl;
             if (head > 1) {
                 return currentLvl + (head) * resolve(currentLvl - 1)
                         + resolve(number - head * currentLvl);
              } else {
                 return number - currentLvl + 1 + (head)
                         * resolve(currentLvl - 1)
                         + resolve(number - currentLvl);
              }
          }
      }
 
     public int scale(int a, int b) { //指数运算
         int res = 1;
         for (int i = 0; i < b; i++) {
              res = a * res;
          }
         return res;
      }
 }
 
 class EnumerateAlgrithm implements Algrithm {// 遍历算法,o(NLogN)
 
      @Override
     public int resolve(int number) {
         int sum = 0;
         for (int i = 0; i <= number; i++) {
              sum += findInSingleNum(i);
          }
         return sum;
      }
 
     private int findInSingleNum(int number) {//单个数中包含'1'数量
         int res = 0;
         while (number > 0) {
             if (number % 10 == 1) {
                  res++;
              }
              number = number / 10;
          }
         return res;
      }
 }
 
 class ReferedAlgrithm implements Algrithm {//原作者的算法,o(LogN)
      @Override
     public int resolve(int n) {
         int count = 0;
         int factor = 1;
         int lower;
         int current;
         int higher;
         while (n / factor != 0) {
              lower = n - (n / factor) * factor;
              current = (n / factor) % 10;
              higher = n / (factor * 10);
             switch (current) {
             case 0:
                  count += higher * factor;
                 break;
             case 1:
                  count += higher * factor + lower + 1;
                 break;
             default:
                  count += (higher + 1) * factor;
              }
              factor *= 10;
          }
         return count;
 
      }
 }
 
 public class getOne {
 
     public static void calculateWith(Algrithm al) {
         long start = System.nanoTime();
         int res = al.resolve(100000000);
         long end = System.nanoTime();
         System.out.println(al.getClass().getName()+":"+res);
          System.out.println("time cost:" + (end - start) + "ns");
     }     public static void main(String[] arg) {
      ReferedAlgrithm test = new ReferedAlgrithm();
      test.resolve(521);
          getOne.calculateWith(new RecursiveAlgrithm());
          getOne.calculateWith(new ReferedAlgrithm());
          getOne.calculateWith(new EnumerateAlgrithm());
    }
 }由于ReferedAlgrithm和RecursiveAlgrithm的算法太快，以至于以毫秒计时都是0ms,因此改用纳秒
output:
puzzles.RecursiveAlgrithm:80000001
time cost:96940ns
puzzles.ReferedAlgrithm:80000001
time cost:4191ns
puzzles.EnumerateAlgrithm:80000001
time cost:25053647670ns
可以看到原作者的算法是最快的，递归算法虽然算法复杂度同为o(LogN)，不过递归在性能上不如循环，因此也差了一个数量级
而最后o(NLogN)复杂度的算法，性能则整整差了6个数量级以上...
这个差距，大概抵得上20年的硬件性能的发展了吧.
各位有兴趣也可以用C#分别实现下这几种算法，看看和java耗时相比如何^^