算法复杂度介绍

2020-06-08  本文已影响0人  myth小艾

算法复杂度

为什么需要复杂度?

解决问题的代码过程有很多种~ 谁优谁劣。一般有两个指标,一般更更多在意第一个指标,因为时间越短,价值越大,空间可以拿钱就可以堆出来~

  1. 时间复杂度 用大写的O表示 计算的耗时
  2. 空间复杂度 用大写的S表示 所需要的临时空间 解释下跑代码,有三种数据空间,输入代码大小跑代码所需要的内存(变量声明等)产出结果的大小,这里的临时空间才是指的空间复杂度,因为输入和输出都是定值,顶多,格式化和优化下代码,相差不大,下面就不具体介绍了,只介绍下时间复杂度

那么时间复杂度怎么区分?

找出算法的基本语句(增长最快的项),展开计算,保留最高项,系数化为1

分别有

//O(1)  常数阶  - 没有迭代语句
function demo1(){
    if(condition)return xx1;
    return xx2;
}
//O(logn)    对数阶   下面是求树的镜像 下面有题目地址   运行次数成指数增长  2  4  6  8
var mirrorTree = function(root) {
  if(!root) return null
  let left=root.left
  root.left=mirrorTree(root.right)
  root.right=mirrorTree(left)
  return root
};

//O(n)        线性阶     循环一遍n
for (let i=0,len=arr.length;i<len;i++) {
   
}
//O(nlogn) nlogn阶  指数增长在加个循环
var mirrorTree = function(root) {
    if (root == null) {
        return null
    }
    let stack = [root]
    while (stack.length != 0) {
        let size = stack.length
        for (let i = 0; i < size; i++) {
            let node = stack.shift()
            node.left != null ? stack.push(node.left) : 0
            node.right != null ? stack.push(node.right) : 0
            let temp = node.left
            node.left = node.right
            node.right = temp
        }
    }
    return root
};


//O(n²)    平方阶   -冒泡排序双层for循环   循环的次数去除常数为n*n
for (let i=0,len=arr.length;i<len;i++) {
    for (let j = 0;j<len-i-1;j++) {
        if(arr[j]>arr[j+1]){
            arr[j]=arr[j+1]+arr[j];
            arr[j+1] = arr[j]-arr[j+1];
            arr[j] = arr[j] - arr[j+1];
        }
    }
}
//O(n³)    立方阶   三层for循环
for(i=1; i<=n; i++)
    for(j=1; j<=n; j++)
        for(k=1; k<=n; k++)
            s++;

题目地址:leetCode二叉树镜像

时间复杂度阶级与所花时间对比
在数据量一定大的时候的优劣
上一篇 下一篇

猜你喜欢

热点阅读