美文网首页
算法导论练习2.2-3算法导论练习2.2-3算法导论练习2.2-

算法导论练习2.2-3算法导论练习2.2-3算法导论练习2.2-

作者: 恋与1 | 来源:发表于2018-01-29 00:16 被阅读0次

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

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

数学证明过程

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

以下是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次下的试验平均结果。代入数字,与公式的答案相符。证明完毕。

相关文章

  • 算法导论练习2.2-3算法导论练习2.2-3算法导论练习2.2-

    题目是:再次考虑线性查找问题(参见联系2.1-3)。假定要查找的元素等可能地为数组中地任意元素,平均需要检查输入序...

  • 算法导论练习2.2-3

    题目是:再次考虑线性查找问题(参见联系2.1-3)。假定要查找的元素等可能地为数组中地任意元素,平均需要检查输入序...

  • 数据结构与算法参考书籍

    数据结构与算法分析 算法 算法导论 java编程思想

  • 好文章索引

    算法 《算法导论》快速指南:我是如何10天入门算法导论的。 - 渗透之美 - 知乎专栏 推荐内容索引 - 老赵点滴...

  • 算法导论笔记

    读算法导论 记录一下读算法导论的过程 1.算法 如果问我什么是算法(思考中) 利用数据结构,考虑时间以及空间效率,...

  • 给我巨大影响的技术书籍

    算法《算法概论》《算法设计与分析基础》 Anany Levitin《算法引论》Udi Manber《算法导论》《什...

  • 参考书籍

    《啊哈! 算法》 《算法导论》(原书第三版)

  • C++快速排序(算法),小白必备!拿走不谢!

    <算法导论>上面的算法逻辑 QUICKSORT(A, p, r)//快速排序算法 if (p < r ) { q ...

  • 快排【算法导论】

    注:学习算法导论,按照标准伪代码理解翻译为java实现,如有兴趣理解整个过程的细节,建议阅读《算法导论》第7章:快...

  • 算法导论

    分析 loop-invariant • A technique to prove that an algorith...

网友评论

      本文标题:算法导论练习2.2-3算法导论练习2.2-3算法导论练习2.2-

      本文链接:https://www.haomeiwen.com/subject/uoetzxtx.html