算法-常见的时间复杂度

三味码屋 2021年09月08日 1,126次浏览

常见复杂度及示例

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$)

示例:

  1. 快速排序;
  2. 归并排序。

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!$)