首页 > 编程语言 >数据结构-绪论2(算法,时间复杂度)

数据结构-绪论2(算法,时间复杂度)

时间:2024-07-22 23:25:05浏览次数:16  
标签:外层 绪论 int 复杂度 内层 算法 循环 数据结构

算法的基本概念

算法是什么

             程序=数据结构+算法

算法的五个特性

有穷性

确定性

可行性

输入

输出

算法的复杂度

时间复杂度

算法时间复杂度
事前预估算法时间开销T(n)与问题规模n的关系

这里以一层,两层,多层循环为例

一层循环

for(int i=0;i<n;i++)
{
    i++;
}

这个很容易就看出来,复杂度为O(n),时间开销和n关系

如果换一个呢

int i = n * n;
while(i != 1){
    i = i / 2;
}

这个便不容易看出,这里讲一下我的解题思路

1.列出循环次数t和每次循环i的值,

2.找到t和i的关系

3.确定循环停止条件

4.联立求解

在这里详细写一下

1

t0123
in^2(n^2)/2(n^2)/4(n^2)/8

2.

i=n^2 \over t^2

3.结束循环的时候,i=1,

4.

n^2 \over t^2=1

求解

T=O(\log_{2}{n})

同样,对于下面这个问题

while(i<n){
    i*=2;
}

也不难求解

两层循环

对于两层循环,本质是求解内层循环的代码块执行次数

1.求出外层循环次数变化(i值的变化)

2列出内层循环代码块执行次数

3.求和

举个栗子

for(int i=1;i<=n;i++){
    for(int j=1;j<=2*i;j++){
        m++;        
    }
}
外层1234
内层代码块次数2468

不难看出,外层执行n次,内层每次是2*i次,进行一个求和即可

最终结果为n(n+1),即为O(n^2)

当内层循环与外层循环无关的时候,如下

for(int i=1;i<=n;i++){
    for(int j=1;j<=m;j++){
          代码块(无关代码)        
    }
}

外层每次循环,内层都执行m次,所以复杂度为O(m*n)

多层循环

三层循环可以看成内层循环是两层循环的两层循环,多层循环也可以这样看做。

同时,下面是一些常用的大小比较

总结

时间复杂度是算法时间开销T(n)与问题规模n的关系

标签:外层,绪论,int,复杂度,内层,算法,循环,数据结构
From: https://blog.csdn.net/gzsn_/article/details/140534061

相关文章

  • 《Java初阶数据结构》----1.<时间复杂度&空间复杂度计算>
    目录算法效率:一、时间复杂度的计算1.1时间复杂度的表示1.2常见时间复杂度大小排序 1.3计算示例冒泡排序的时间复杂度二分查找的时间复杂度 阶乘递归factorial的时间复杂度斐波那契递归的时间复杂度二、空间复杂度的计算冒泡排序的空间复杂度计算fibonacci的空间复......
  • 时间和空间复杂度
    目录 一、时间复杂度 1.1定义1.2分类二、空间复杂度 2.1定义 2.2分类 2.3重要性 在计算机科学中,算法的效率是一个至关重要的概念。评估算法的效率通常涉及两个主要方面:时间复杂度和空间复杂度。这两个概念不仅帮助我们理解算法在处理数据时的表现,还为开......
  • 数据结构——堆(C语言版)
    树    树的概念:        树(Tree)是一种抽象数据结构,它由节点(node)的集合组成,这些节点通过边相连,把节点集合按照逻辑顺序抽象成图像,看起来就像一个倒挂着的树,也就是说数据结构中的树是根成朝上,叶子朝下。        树形结构中,⼦树之间不能有交集,否则就不......
  • 片集 - 数据结构 - 1
    欢迎来看“片”(的简介)由于-\(看片\)-生涯转瞬即逝,于是我选择对“\(片\)”进行一定的总结:相信你一定看懂了由于开始的时间有一点晚,就姑且认为我以后会慢慢补充吧......\(CF1270H\)\(Number\)\(of\)\(Components\)解:线段树首先我们可以发现连通块都是以区间的形式存在的......
  • 7.22数据结构
    笔记链表一.链表的引入1.1总结顺序表的优缺点    1)优点:能够直接通过下表进行定位元素,访问效率高,对元素进行查找修改比较快    2)不足:插入和删除元素需要移动大量的元素,效率较低    3)缺点:存储数据元素有上限,当达到MAX后,就不能再添加元素了、1.2链......
  • 【数据结构】:链表实现洗牌功能
    此操作包含的基本功能有:组牌:组建52张扑克牌四种花色:“♥️”,“♠️”,“⬛️”,“♣️”每种花色13张牌:1~13洗牌:将52张扑克牌打乱顺序发牌:给三个人每人发5张牌扩展功能:清牌:将每人手中牌按照面值进行从大到小排序Card类在此类中,我们将完成对每一张牌的构造类......
  • 数据结构与算法总结——线性表
    目录2线性表2.1线性表的定义2.2线性表的基本操作2.2顺序表2.2.1顺序表的定义2.2.2顺序表的基本操作2.3链式表2.3.1链表的定义2.3.2链表的分类2.3.3单向链表2.3.3.1结点设计2.3.3.2链表的初始化2.3.3.3数据的插入2.3.3.4数据的删除2.3.3.5销毁链......
  • 手撕数据结构01--单链表(附源码)
    目录1.链表的概念和结构1.1链表的概念1.2单链表结构2.实现单链表2.1节点定义2.2链表功能2.3 创建节点2.4尾插2.5头插2.6打印2.7尾删2.8头删2.9查找2.10指定位置插入2.11指定位置之后插入2.12删除pos节点2.13删除pos之后的节点2.14销毁链表......
  • 01-复杂度3 二分查找 陈越、何钦铭数据结构
    题目可以满分通过的答案:`PositionBinarySearch(ListL,ElementTypeX){Positionleft=1;Positionright=L->Last;while(left<=right){Positioncenter=(left+right)/2;if(L->Data[center]>X){right=center-1;}elseif(L->Data......
  • 数据结构-C语言-排序(3)
            代码位置:test-c-2024:对C语言习题代码的练习(gitee.com)一、前言:1.1-排序定义:        排序就是将一组杂乱无章的数据按照一定的规律(升序或降序)组织起来。(注:我们这里的排序采用的都为升序)1.2-排序分类:常见的排序算法:插入排序a. 直接插......