算法导论练习2.2-3

题目是:再次考虑线性查找问题(参见联系2.1-3)。假定要查找的元素等可能地为数组中地任意元素,平均需要检查输入序列地多少元素?最坏情况又如何呢?用θ记号给出线性朝朝地平均情况和最坏情况地运行时间。证明你的答案。

开始看算法导论,网上搜了一下这一题的思路,没有找到正确答案,都是简单的(1+n)/2。

因此自己动笔写了写,答案应该是(1-(1-p)^n)/p (p是概率,n是数组的长度)。

以下是证明过程与C语言程序验证:

IMG_0029(20180314-102808).jpg

过程中的难点就是等差等比数列的求和,网上搜下公式应该不难。

以下是C语言代码的验证:


#include

#include

#include

int main()

{

    int v = 23;        //v为某个值

    int count = 50000; //样本测试的次数

    int size = 10;    //数组的大小

    double p = 0.2;    //是v的概率

    int h;

    double sumIndex = 0;

    int arr[size]; //定义数组

    srand((unsigned)time(NULL));

    for (int k = 0; k < count; k++)

    {

        for (int i = 0; i < size; i++)

        {

            if ((double)rand() / RAND_MAX <= p)

            {

                arr[i] = v;

            }

            else

            {

                arr[i] = 1;

            }

        }

        for (int j = 0; j < size; j++)

        {

            if (arr[j] == v || (j == (size - 1) && arr[j] != v))

            {

                v = 0;

                sumIndex += (j + 1);

                break;

            }

        }

        v = 23;

    }

    printf("%f", (double)(sumIndex / count));

    return 0;

}

4.459680是大小为10的数组在5w次下的试验平均结果。代入数字,与公式的答案相符。证明完毕。

©著作权归作者所有,转载或内容合作请联系作者
平台声明:文章内容(如有图片或视频亦包括在内)由作者上传并发布,文章内容仅代表作者本人观点,简书系信息发布平台,仅提供信息存储服务。

推荐阅读更多精彩内容

  • Chapter 2 插入排序 线性查找 选择算法 归并排序算法 二分查找算法 冒泡排序 插入排序 循环不...
    只是无情绪阅读 1,481评论 0 1
  • 人生的路上 并不是你在哪里放一个门框 那里便是唯一的出口 世界再大 你唯一始终拥有的也只是自己 你即使原点 也是终...
    红尘多扰阅读 377评论 0 2
  • 文/赵欣,两岁男孩的妈妈,正面管教讲师和非暴力沟通践行者。 -正文开始- 最近带儿子在早教中心,经常会遇到攻击性比...
    赵欣Ella阅读 657评论 3 6
  • 《射雕英雄传》这部书.它巧妙地利用了宋朝时宋、金、蒙古三国的微妙关系,为我们讲述了一代英雄——郭靖的成长过程,以及...
    张亚霖阅读 283评论 0 0
  • 这是我第一次写小说类的读书笔记,抑或叫书评吧。确实有些无从下手,不知道我是先介绍下这本书写的是——一个古板、刻薄、...
    强说愁阅读 621评论 0 0