BigO

##使用BigO来衡量程序码的时间复杂度(time complexity)是很重要的一件事情,接下来让我们来学习吧
以下为阅读[https://pjchender.blogspot.com/2017/09/big-o-notation-time-complexity.html] PJ老师的阅後心得,并且搭配JavaScript资料结构与演算法!!!

• BigO使用Worst case

BigO(1)

只输出该array的index值0、1,即为常数1

function BigO(array){
    console.log(array[0])
    console.log(array[1])
}
BigO([0,1,2,3,4,5])
//0
//1

BigO(n)

输出n即线性输出,若输入10000次即输出10000次

function BigO(array){
   for(let i=0; i<array.length; i++){
       console.log(array[i])
   }
}
BigO([0,1,2,3,4,5])
// 0
// 1
// 2
// 3
// 4
// 5

BigO(n^2)

输出n即为平方,要特别注意BigO(n^2)是很差的算法了!!!

function BigO(array){
   for(let i=0; i<array.length; i++){
       for(let j=0; j<array.length; j++){
           console.log(array[j])
       }
   }
}
BigO([0,1])
// 0
// 1
// 0
// 1

BigO(log n)

虽然输入是线性,但因为每次都对半砍,所以为BigO(logn)

let array1 = [1,3,5,7,9,11]

function BigO(array, key){
    let min = 0 
    let max = array.length -1
    while(min <= max){
        let middle = Math.floor((min + max) /2)
        
        if(array[middle] > key) {
            max = array[middle -1]
        }else if(array[middle] < key){
            min = array[middle +1]
        }else{
            return middle
        }
    }
}
console.log(BigO(array1, 5 ))
//index为2