@阅读目录 一.O(logn)代码小证明 二.典型时间复杂度分析 三.常见的算法
𝑙𝑜𝑔𝑁 - 对分查找𝑙𝑜𝑔𝑁 - 欧几里得算法𝑙𝑜𝑔𝑁 - 幂运算n2 - 选择排序n2 - 插入排序2n - 汉诺塔2n - 斐波那契数最大公约数
一.O(logn)代码小证明
我们先来看下面一段代码:
int cnt = 1;
while (cnt < n)
{
cnt *= 2;
//时间复杂度为O(1)的程序步骤序列
}
由于cnt每次在乘以2之后都会更加逼近n，也就是说，在有x次后，cnt将会大于n从而跳出循环，所以2𝑥 = 𝑛 ,也就是𝑥=𝑙𝑜𝑔2𝑛，所以这个循环的复杂度为O(logn)
二.典型时间复杂度
c
c
c 常数
l
o
g
N
logN
logN 对数级
l
o
g
2
N
log ^ 2N
log2N 对数平方根
N
N
N 线性级
N
l
o
g
N
NlogN
NlogN
N
2
N ^ 2
N2 平方级
N
3
N ^ 3
N3 立方级
2
N
2 ^ N
2N 指数级 由此我们可以得知，𝑙𝑜𝑔𝑁的算法效率是最高的
三.常见的算法
1. 𝑙𝑜𝑔𝑁-对分查找
(int)BinarySearch:(NSArray *)originArray element:(int)element
{
int low, mid, high;
low = 0; high = (int)originArray.count - 1;
while (low <= high) {
mid = (low + high) / 2;
if ([originArray[mid] intValue] < element) {
low = mid + 1;
} else if ([originArray[mid] intValue] > element) {
high = mid -1;
} else {
return mid;
}
}
return -1;
}
2. 𝑙𝑜𝑔𝑁-欧几里得算法
求最大公约数的一个有效的算法，最古老的著名算法之一：欧几里得算法。 递归的定义为： 用gcd(m,n) 表示整数m和n的最大公约数：
如果m%n==0，那么gcd(m,n) 为n。否则，gcd(m,n) 就是gcd(n，m%n)。
证明：假设m%n=r，那么m=(m/n)*n+r，能整除m和n的任意数字都必须也能整除r。因此 gcd(m,n) 和gcd(n,r)是一样的。
(unsigned int)Gcd:(unsigned int)m n:(unsigned int)n
{
unsigned int Rem;
while (n > 0) {
Rem = m % n;
m = n;
n = Rem;
}
return m;
}
3. 𝑙𝑜𝑔𝑁 - 幂运算
(long)Pow:(long)x n:(unsigned int)n
{
if (n == 0) {
return 1;
}
if (n == 1) {
return x;
}
if ([self isEven:n]) {
return [self Pow:x * x n:n / 2];
} else {
return [self Pow:x * x n:n / 2] * x;
}
}
(BOOL)isEven:(unsigned int)n
{
if (n % 2 == 0) {
return YES;
} else {
return NO;
}
}
4. n2 选择排序
5. n2 插入排序
6. 2n 汉诺塔
7. 2n - 斐波那契数
//递归循环，冗余算法
public static long fib(long index){
if (index == 0){
return 0;
}else if (index == 1)
return 1;
else
return fib(index-1) + fib(index - 2);
}
//递归循环：赋值算法。时间复杂度为O(n)
public class ImprovedFibonacci {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
System.out.println("Enter an index for the Fibonacci number: ");
int index = input.nextInt();
System.out.println("Fibonacci number at index "+index+" is "+fib(index));
}
public static long fib(long n){
long f0 = 0;
long f1 = 1;
long f2 = 1;
if (n == 0)
return f0;
else if (n == 1)
return f1;
else if (n == 2)
return f2;
for(int i=3; i<=n; i++){
f0 = f1;
f1 = f2;
f2 = f0 + f1;
}
return f2;
}
}
8、最大公约数 - 1
时间复杂度O(n)
public class GCD1 {
public static void main(String[] args) {
Scanner input = new Scanner(System.in);
System.out.println("Enter first integer: ");
int m = input.nextInt();
System.out.println("Enter second integer: ");
int n = input.nextInt();
System.out.println("The greatest common divisor for "+ m +" and "+n+" is "+gcd(m,n));
}
public static int gcd(int m, int n){
int gcd = 1;
if (m % n == 0)
return n;
for (int k = (n/2); k>=1; k--){
if (m%k == 0 && n%k == 0){
gcd = k;
break;
}
}
return gcd;
}
}
8、最大公约数 - 2（欧几里得算法）
时间复杂度O(logn)
public static int gcd(int m,int n){
if (m%n == 0)
return n;
else
return gcd(n,m%n);
}
最后，也是最基本的最重要的
当题目的数据范围达到了
1
0
18
10^{18}
1018的时候，很显然就要用O(logn)的算法或数据结构了
参考：
https://www.cnblogs.com/linhaostudy/p/11659846.html Java语言程序设计第八版-进阶版-Y.Daniel Liang