提供了编程的基础技术教程

zl程序教程

您现在的位置是：首页 >  后端

当前栏目

算法入门

算法入门
2023-09-14 09:00:17 时间

很多学过算法的童鞋，都觉得老师讲的算法里面排序占有很大的比例，可以说排序是算法的重点，这是为什么呢？

原因是，很大部分的算法仅在数据经过排序后才管用，例如我们最经典的二分查找。

首先先介绍下最基本的两种数据类型：数组和链表

数组：是内存相邻的一个队列

链表：内存不相邻的队列，每个元素都会存下下一个元素的地址

很明显,两种数据类型的操作的时间复杂度：

  数组 链表
读取 O(1) O(n)
插入 O(n) O(1)
删除 O(n) O(1)

下面来介绍下上面说到的时间复杂度（大O表示法）

大O表示法：O(操作次数)

常见的几种大O运行时间：

由快到慢：O(log n)、O(n)、O(n * log n)、O(n^2)、O(!n)

我们的二分查找就是O(log n)了

 最后我们介绍下最经典的二分查找吧：

let arr = [1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]
function sort(arr, num) {
    let low = 0
    let high = arr.length - 1
    let mid = Math.floor((low + high) / 2)
    while (low <= high) {
        if(arr[mid] === num) {
            return mid
        } else if (arr[mid] < num) {
            low = mid + 1
        } else {
            high = mid - 1
        }
        mid = Math.floor((low + high) / 2)
    }
    return null
}

很明显这种算法每次都会把范围缩减一半，时间复杂度用大O表示法表示O(log n)，最坏情况下总共会计算log2 n次

相关文章