它是一种表示法,决定算法运行的速度有多快或多慢。这个速度不是由秒决定的,而是由算法的运行时间随着元素的增加而增加多少决定的。
大o是时间和大小的关系。在整篇文章中,您将看到包含这些度量的图表,并且您将在实践中更好地理解它们。我们有两种类型的复杂性(空间和时间)。
时间复杂度: 确定执行与输入大小成正比的算法所需的时间。
空间复杂度: 确定将分配多少内存来查找我们需要的项目。
示例:
康斯坦特节奏 o(1):
示例:
function increment(value: number){ return ++value } function decrement(value: number){ return --value }
const fruits = ["apple", "orange", "grape", "banana"] function getitem(items: string[], index: number) { return items[index] } const item = getitem(fruits, 2) console.log(`fruit: ${item}`) // "grape"
const animes = ["one piece", "dragon ball", "naruto", "demon slayer"] function getfirstelement(items: string[]){ return items[0] }
const animes = ["one piece", "dragon ball", "naruto", "demon slayer"] function getlastelement(items: string[]){ return items[item.length - 1] } let lastelement = getlastelement(animes) console.log(`last element: ${lastelement}`)
线性时间 o(n):
示例:
const numbers = [0, 4, 8, 2, 37, 11, 7, 48] function getmaxvalue(items: number[]) { let max = numbers[0]; for (let i=0; i <= items.length; i++){ if(items[i] > max) { max = items[i] } } return max; } let maxvalue = getmaxvalue(numbers) console.log(`max value: ${maxvalue}`)
对数时间 o(log n)
示例:
const numbers = [0, 9, 24, 78, 54, 88, 92, 100, 21, 90] function binarysearch(nums: number[], target: number) { let left = 0; let right = nums.length - 1; while (left <= right) { let middle = math.floor((right + left) / 2); if (nums[middle] === target) { return middle; } else if (nums[middle] < target) { left = middle + 1; } else { right = middle - 1; } } return -1; } let gettarget = binarysearch(numbers, 92) console.log(`target: ${gettarget}`)
log2(10) = 3.4
log2(20) = 4.3
log2(40) = 5.3
线性/拟线性时间 o(n log n)
function merge(arr, left, middle, right) { const leftarraysize = middle - left + 1; const rightarraysize = right - middle; const leftarray = new array(leftarraysize); const rightarray = new array(rightarraysize); for (let i = 0; i < leftarraysize; i++) { leftarray[i] = arr[left + i]; } for (let j = 0; j < rightarraysize; j++) { rightarray[j] = arr[middle + 1 + j]; } let i = 0; let j = 0; let k = left; while (i < leftarraysize && j < rightarraysize) { if (leftarray[i] <= rightarray[j]) { arr[k] = leftarray[i]; i++; } else { arr[k] = rightarray[j]; j++; } k++; } while (i < leftarraysize) { arr[k] = leftarray[i]; i++; k++; } while (j < rightarraysize) { arr[k] = rightarray[j]; j++; k++; } } function mergesort(arr, left = 0, right = arr.length - 1) { if (left < right) { const middle = math.floor((left + right) / 2); mergesort(arr, left, middle); mergesort(arr, middle + 1, right); merge(arr, left, middle, right); } return arr; } function testmergesort() { const arr1 = [64, 34, 25, 12, 22, 11, 90]; console.log("sorted array:", mergesort([...arr1])); } testmergesort();
二次时间 o(n²)
示例:
function creatematrix() { const matrix = [ [2,4,5,], [89,0,12], [13,76,89] ]; for (let i = 0; i < matrix.length; i++) { for (let j = 0; j < matrix[i].length; j++) { console.log(`element at [${i}][${j}]: ${matrix[i][j]}`); } } }
时间指数 o(2ˆn)
function fibonacci(n) { if(n <= 1){ return n } else { return fibonacci(n-1) + fibonacci(n-2) } }
阶乘时间 o(n!)
示例:
function factorialIterative(n) { if (n === 0 || n === 1) { return 1; } let result = 1; for (let i = 2; i <= n; i++) { result *= i; } return result; }
以上就是大 O 符号的详细内容,更多请关注php中文网其它相关文章!
每个人都需要一台速度更快、更稳定的 PC。随着时间的推移,垃圾文件、旧注册表数据和不必要的后台进程会占用资源并降低性能。幸运的是,许多工具可以让 Windows 保持平稳运行。
Copyright 2014-2025 https://www.php.cn/ All Rights Reserved | php.cn | 湘ICP备2023035733号