大 O 符号
来源:dev.to
2024-12-22 14:34:06
0浏览
收藏
今天golang学习网给大家带来了《大 O 符号》,其中涉及到的知识点包括等等,无论你是小白还是老手,都适合看一看哦~有好的建议也欢迎大家在评论留言,若是看完有所收获,也希望大家能多多点赞支持呀!一起加油学习~
它是一种表示法,决定算法运行的速度有多快或多慢。这个速度不是由秒决定的,而是由算法的运行时间随着元素的增加而增加多少决定的。
大o是时间和大小的关系。在整篇文章中,您将看到包含这些度量的图表,并且您将在实践中更好地理解它们。我们有两种类型的复杂性(空间和时间)。
时间复杂度: 确定执行与输入大小成正比的算法所需的时间。
空间复杂度: 确定将分配多少内存来查找我们需要的项目。
为什么要研究这个?
- 通过它,您可以确定算法的可扩展性
- 大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):
- 执行时间与数组大小成正比
- 排序和二分搜索算法
- 仅使用一个循环进行迭代
示例:
- 为了找到 10 个项目的数组中最大的数字,我将滚动所有项目,直到找到它。
- 在最坏的情况下,最大的数字将是最后一个。
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)
- 输入大小增加n,执行时间增加log n,时间以对数比例增长。
- 记住 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}`)
- 为了更好地理解对数增长,让我们看如下:我们在示例中使用的数组有 10 个输入,因此:
log2(10) = 3.4
log2(20) = 4.3
log2(40) = 5.3
- 下面的图表将更容易理解:
线性/拟线性时间 o(n log n)
- 算法的时间复杂度是指执行n次对数运算。
- o(log(n)) 和 o(n) 的混合。
- 归并排序就是一个结构示例。
- 适度增长。
- 一部分以 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²)
- 随着输入数量的增加,执行时间呈二次方增加。
- 阅读矩阵。
- 基本上当需要 2 个嵌套循环时
- 冒泡排序
示例:
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 符号》的介绍应该让你收获多多了吧!欢迎大家收藏或分享给更多需要学习的朋友吧~golang学习网公众号也会发布文章相关知识,快来关注吧!
版本声明
本文转载于:dev.to 如有侵犯,请联系study_golang@163.com删除
查看更多
最新文章
-
- 文章 · 前端 | 10分钟前 |
- React日历控件推荐及使用教程
- 135浏览 收藏
-
- 文章 · 前端 | 12分钟前 |
- JavaScript调试技巧:debugger使用全解析
- 303浏览 收藏
-
- 文章 · 前端 | 17分钟前 |
- CSS表单样式美化教程
- 233浏览 收藏
-
- 文章 · 前端 | 17分钟前 |
- CSS中margin使用方法详解
- 158浏览 收藏
-
- 文章 · 前端 | 28分钟前 | JavaScript 用户体验 鼠标指针 CSScursor 自定义图像
- CSS修改鼠标指针样式方法
- 276浏览 收藏
-
- 文章 · 前端 | 37分钟前 |
- HTML5time标签如何提升SEO?
- 435浏览 收藏
-
- 文章 · 前端 | 52分钟前 | 字符串处理 unicode codePointAt 代理对 码元
- ES6字符串codePointAt处理Unicode详解
- 241浏览 收藏
-
- 文章 · 前端 | 1小时前 |
- JavaScript中indexOf查找元素位置方法
- 228浏览 收藏
-
- 文章 · 前端 | 1小时前 | CSS JavaScript HTML表格 悬停效果 :hover伪类
- HTML表格悬停效果添加方法,CSS实现教程
- 354浏览 收藏
-
- 文章 · 前端 | 1小时前 |
- BOM如何获取用户时区信息?
- 412浏览 收藏
查看更多
课程推荐
-
- 前端进阶之JavaScript设计模式
- 设计模式是开发人员在软件开发过程中面临一般问题时的解决方案,代表了最佳的实践。本课程的主打内容包括JS常见设计模式以及具体应用场景,打造一站式知识长龙服务,适合有JS基础的同学学习。
- 542次学习
-
- GO语言核心编程课程
- 本课程采用真实案例,全面具体可落地,从理论到实践,一步一步将GO核心编程技术、编程思想、底层实现融会贯通,使学习者贴近时代脉搏,做IT互联网时代的弄潮儿。
- 509次学习
-
- 简单聊聊mysql8与网络通信
- 如有问题加微信:Le-studyg;在课程中,我们将首先介绍MySQL8的新特性,包括性能优化、安全增强、新数据类型等,帮助学生快速熟悉MySQL8的最新功能。接着,我们将深入解析MySQL的网络通信机制,包括协议、连接管理、数据传输等,让
- 497次学习
-
- JavaScript正则表达式基础与实战
- 在任何一门编程语言中,正则表达式,都是一项重要的知识,它提供了高效的字符串匹配与捕获机制,可以极大的简化程序设计。
- 487次学习
-
- 从零制作响应式网站—Grid布局
- 本系列教程将展示从零制作一个假想的网络科技公司官网,分为导航,轮播,关于我们,成功案例,服务流程,团队介绍,数据部分,公司动态,底部信息等内容区块。网站整体采用CSSGrid布局,支持响应式,有流畅过渡和展现动画。
- 484次学习
查看更多
AI推荐
-
- 边界AI平台
- 探索AI边界平台,领先的智能AI对话、写作与画图生成工具。高效便捷,满足多样化需求。立即体验!
- 392次使用
-
- 免费AI认证证书
- 科大讯飞AI大学堂推出免费大模型工程师认证,助力您掌握AI技能,提升职场竞争力。体系化学习,实战项目,权威认证,助您成为企业级大模型应用人才。
- 405次使用
-
- 茅茅虫AIGC检测
- 茅茅虫AIGC检测,湖南茅茅虫科技有限公司倾力打造,运用NLP技术精准识别AI生成文本,提供论文、专著等学术文本的AIGC检测服务。支持多种格式,生成可视化报告,保障您的学术诚信和内容质量。
- 542次使用
-
- 赛林匹克平台(Challympics)
- 探索赛林匹克平台Challympics,一个聚焦人工智能、算力算法、量子计算等前沿技术的赛事聚合平台。连接产学研用,助力科技创新与产业升级。
- 641次使用
-
- 笔格AIPPT
- SEO 笔格AIPPT是135编辑器推出的AI智能PPT制作平台,依托DeepSeek大模型,实现智能大纲生成、一键PPT生成、AI文字优化、图像生成等功能。免费试用,提升PPT制作效率,适用于商务演示、教育培训等多种场景。
- 548次使用
查看更多
相关文章
-
- 优化用户界面体验的秘密武器:CSS开发项目经验大揭秘
- 2023-11-03 501浏览
-
- 使用微信小程序实现图片轮播特效
- 2023-11-21 501浏览
-
- 解析sessionStorage的存储能力与限制
- 2024-01-11 501浏览
-
- 探索冒泡活动对于团队合作的推动力
- 2024-01-13 501浏览
-
- UI设计中为何选择绝对定位的智慧之道
- 2024-02-03 501浏览