文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 高等教育 > 工学 > 算法作业-寻找多数元素
侵权投诉

算法作业-寻找多数元素

寻找多数元素

1,算法分析

如书中所示,若将A[n]中的每个元素均与其他元素比较,并对每一个元素计数,则需1+2+3+....+(n-1)=n*(n-1)/2次运算。

若对A[n]中的数据排序,最多需要的代价为Θ(n log n)

还有一种方法是中间元素法,时间复杂度为θ(n),但算法过于复杂

有一种算法可以很大程度减少时间复杂度,并且算法简单,可以称为候选元素递归法 具体过程如下,

c=A[1],计算器设为count=1,如果下一位数据等于A[1],count=count+1,否者count=count-1,依次往后比较,最后若count>0,return c,否者比较A[i++](i初始为1)直到出现返回值c,结束;若i>=n仍未返回c,返回0

这种算法最少要比较(n-1)次,最多仍需(n-1)*n/2 次

以下为方法1中的编程

算法如下

#include<stdio.h>

#include<malloc.h>

int candidate(int*A,int m,int n);

void main()

{

int*A;

int i,c,j,n;

int count=0;

printf("请输入数据个数:");

scanf("%d",&n);

A=(int*)malloc(sizeof(int)*n);

for(i=0;i<n;i++)

{

第1页

你可能喜欢

热门文档

相关文档

  • 西电算法大作业,寻找多数元素

    寻找多数元素的算法试验报告一. 问题描述令 A[1...n] 是一个整数序列,A 中的整数 a 如果在 A 中出现的次数多于 ? n / 2 ? ,那么 a 称为多数元素。...

  • 算法设计大作业之寻找多数元素

    算法设计大作业之寻找多数元素 隐藏>> 寻找最大元素 一,问题描述: 令 A[1…n]是一个整数序列,A 中的整数 a 如果在 A 中出现 的次数多于 ? ? n? ? ?...

  • 寻找多数元素(Majority)(算法设计大作业)

    寻找多数元素(Majority)(算法设计大作业)_计算机软件及应用_IT/计算机_专业资料。本文用C语言对寻找多数元素算法进行实现,并把运行结果进行展示。希望帮到大家。今日...

  • 算法设计——寻找多数元素

    喜欢此文档的还喜欢 算法设计大作业之寻找多数... 7页 免费搜你所想,读你所...算法分析: 将计数器置 1,并令 c=A[1],从 A[2]开始,逐个地扫描元素,如...

  • 寻找多数元素

    算法设计——寻找多数元... 5页 2下载券 算法作业——寻找多数元... 4页 2...题班 姓学 目:级: 名: 号: 寻找多数元素 一、问题描述令 A[1..n] 是...

  • 西电算法设计大作业

    算法设计---寻找多数元素 学号:020105020 姓名:林桥洲 (1)问题提出:令 A[1,2,…n]是一个整数序列,A 中的整数 a 如果在 A 中出现的次数多余 ,那么 a ...

  • 寻找多数元素

    寻找多数元素_计算机软件及应用_IT/计算机_专业资料。寻找多数元素算法代码寻找多数元素 021252 班 02125128 号 谭红光一、Description About the Problem: A majority...

  • 寻找多数元素

    2财富值 西电算法大作业,寻找多数元... 暂无评价 5页 5财富值搜..., 中的整数 a 如果在 A 中出 A 现次数多于 n/2,那么 a 称为多数元素。...

  • 西电算法设计大作业

    算法设计大作业寻找多数元素 班级:021151 学号:02115037 姓名:隋伟哲 (1)问题提出:令 A[1,2,…n]是一个整数序列, A 中的整数 a 如果在 A 中出现的次数...

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email