常见复杂度及示例
O($1$)
示例：
/**
* 算法复杂度示例-O(1)
* 判断数字n是否是偶数
*/
@Test
fun complexity1() {
val n = 1024
assert(n % 2 == 0)
}
O($logn$)
示例：
/**
* 算法复杂度示例-O(logn)
* 数字n转换为二进制数
*/
@Test
fun complexityLogN() {
var n = 1000
var s = ""
while (n > 0) {
s = (n % 2).toString() + s
n /= 2
println("n=$n")
}
println("s = $s")
}
O($\sqrt n$)
示例：
/**
* 算法复杂度示例-O(√n）
* 求数字n的所有约数
*/
@Test
fun complexitySqrtN() {
val n = 1024
val list = mutableListOf<Int>()
for (i in 1..sqrt(n.toFloat()).toInt()) {
if (n % i == 0) {
list.add(i)
list.add(n / i)
}
}
println("list is $list")
}
O($n$)
示例：
/**
* 算法复杂度示例-O(n)
* 求数字n的所有约数
*/
@Test
fun complexityN() {
val n = 1025
val list = mutableListOf<Int>()
for (i in 1..n) {
if (n % i == 0) {
list.add(i)
}
}
println("list is $list")
}
O($nlogn$)
示例：
- 快速排序；
- 归并排序。
O($n^2$)
示例：
/**
* 算法复杂度示例-O(n²)
*/
@Test
fun complexityNSquare() {
val n = 10
val array = arrayOfNulls<IntArray>(n)
for (i in 0 until n) {
val arrayJ = IntArray(n)
array[i] = arrayJ
for (j in 0 until n) {
arrayJ[j] = i * j
println("array[$i][$j]=${array[i]!![j]}")
}
}
}
/**
* 算法复杂度示例-O(n²)
*/
@Test
fun complexityNSquare2() {
val n = 10
println("=========九九乘法口诀表=========")
for (i in 1 until n) {
for (j in 1 until n) {
if (j > i || i == 9) {
println()
break
}
print("$j * $i = ${i * j} ")
}
}
println("=========九九乘法口诀表=========")
}
O($2^n$)
示例：
/**
* 算法复杂度示例-O(2^n)
* n个位数长度的所有二进制数
*/
@Test
fun complexitySquareN() {
fun getB(x: Int, length: Int): String {
var n = x
var s = ""
if (n > 0) {
while (n > 0) {
s = (n % 2).toString() + s
n /= 2
}
} else {
s = 0.toString()
}
val sLength = s.length
val lengthDiff = length - sLength
if (lengthDiff > 0) {
for (i in 0 until lengthDiff) {
s = "0$s"
}
}
return s
}
val n = 3
val list = mutableListOf<String>()
for (i in 0 until 2.toDouble().pow(n.toDouble()).toInt()) {
list.add(getB(i, 3))
}
println("list is $list")
}
O($n!$)
示例：
求元素个数为n的数组的所有排列
复杂度排序
| O($1$) | < | O($logn$) | < | O($\sqrt n$) | < | O($n$) | < | O($nlogn$) | < | O($n^2$) | < | O($2^n$) | < | O($n!$) |