递归与迭代
//求1+2+3+…+n
//递归
fun recursive(n: Int): Int {
return if (n == 0) 0 else n + recursive(n - 1)
}
//迭代
fun iteration(n: Int): Int {
var result = 0
for (i in 1..n) result += i
return result
}
图解：
//使用递归 : recursive(5)
//
//recursive(5)
//5+recursive(4)
//5+4+recursive(3)
//5+4+3+recursive(2)
//5+4+3+2+recursive(1)
//5+4+3+2+1+recursive(0)
//5+4+3+2+1+0
//5+4+3+2+1
//5+4+3+3
//5+4+6
//5+10
//15
//使用迭代 : iteration(5)
//
//0+1=1
//1+2=3
//3+3=6
//6+4=10
//10+5=15
//
//上面两个计算过程所需的步骤都是O(n)。但是两个计算过程的形状不一样。
递归过程是一个先逐步展开而后收缩的形状，在展开阶段，这一计算过程构造起一个推迟进行的操作所形成的的链条（这里是+)，
在收缩阶段才会实际执行这些操作。
这种类型的计算过程由一个推迟执行的运算链条刻画，称为一个递归计算过程。
要执行这种计算过程，就需要维护以后将要执行的操作的轨迹。
在计算1+2+3+…+n时，推迟执行的加法链条的长度就是为了保存其轨迹需要保存的信息量，
这个长度随着n值而线性增长，这样的过程称为线性递归过程。
迭代过程的形成没有任何增长或收缩。对于任意一个n，在计算的每一步，我们需要保存的就只有i,ret，
这个过程就是一个迭代计算过程。
一般来说，迭代计算过程就是那种其状态可以用固定数目的状态变量描述的结算过程。
在计算1+2+…+n时，所需的计算步骤与n成正比，这种过程称为线性迭代过程。
参考：
递归算法的时间复杂度分析
按数量级递增排列，常见的时间复杂度量有：
（1）O(1)：常量阶，运行时间为常量
（2）O(logn)：对数阶，如二分搜索算法
（3）O(n)：线性阶，如n个数内找最大值
（4）O(nlogn)：对数阶，如快速排序算法
（5）O(n^2)：平方阶，如选择排序，冒泡排序
（6）O(n^3)：立方阶，如两个n阶矩阵的乘法运算
（7）O(2^n)：指数阶，如n个元素集合的所有子集的算法
（8）O(n!)：阶乘阶，如n个元素全部排列的算法
参考:
测试
/**
* 时间复杂度： O(1)
*/
private static int test1(int start) {
start = start + 1; //执行一次
return start;
}
/**
* 时间复杂度： O(n)
*/
private static int test2(int start, int n) {
for (int i = 0; i < n; i++) {
start = start + 1; //执行 n 次
}
return start;
}
/**
* 时间复杂度： O(n^2)
*/
private static int test3(int start, int n) {
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
start = start + 1; //执行 n * n 次
}
}
return start;
}
二分查找：O(log2n)
二分查找的基本思想是将n个元素分成大致相等的两部分，取a[n/2]与x做比较，如果x=a[n/2],则找到x,算法中止；
如果x<a[n/2],则只要在数组a的左半部分继续搜索x,如果x>a[n/2],则只要在数组a的右半部搜索x.
时间复杂度即是while循环的次数。
总共有n个元素，
渐渐跟下去就是n,n/2,n/4,…n/2^k（接下来操作元素的剩余个数），其中k就是循环的次数
由于你n/2^k取整后>=1
即令n/2^k=1
可得k=log2n,（是以2为底，n的对数）
所以时间复杂度可以表示O(h)=O(log2n)
package android.util;
class ContainerHelpers {
// This is Arrays.binarySearch(), but doesn't do any argument validation.
static int binarySearch(int[] array, int size, int value) {
int lo = 0;
int hi = size - 1;
while (lo <= hi) {
final int mid = (lo + hi) >>> 1;
final int midVal = array[mid];
if (midVal < value) {
lo = mid + 1;
} else if (midVal > value) {
hi = mid - 1;
} else {
return mid; // value found
}
}
return ~lo; // value not present
}
static int binarySearch(long[] array, int size, long value) {
int lo = 0;
int hi = size - 1;
while (lo <= hi) {
final int mid = (lo + hi) >>> 1;
final long midVal = array[mid];
if (midVal < value) {
lo = mid + 1;
} else if (midVal > value) {
hi = mid - 1;
} else {
return mid; // value found
}
}
return ~lo; // value not present
}
}
冒泡排序算法 : O(n^2)
/**
* 冒泡排序算法
*
* @param array 未排序数组
* @return int[] 排完序数组
* 冒泡排序是將比較大的數字沉在最下面，较小的浮在上面
*/
public static int[] sortBubble(int[] array) {
int temp;
// 第一层循环:表明比较的次数,
// 比如 length 个元素,比较次数为 length-1 次（肯定不需和自己比）
for (int i = 0; i < array.length - 1; i++) {
for (int j = array.length - 1; j > i; j--) {
if (array[j] < array[j - 1]) {
temp = array[j];
array[j] = array[j - 1];
array[j - 1] = temp;
}
}
}
return array;
}