logo资料库

数据结构算法复杂度题目答案.doc

发布时间：2022-06-09 发布人：admin 分类：说明书 资料大小：0.01M 资料格式：doc 举报 版权申诉
第1页 / 共2页
第2页 / 共2页
资料共2页，全文预览结束
    1.For each of the following six program fragments:Give an analysis of the running time(Big-Oh will do) times (1) sum = 0; for (i=0;i k . Solution 1: (1) read N numbers into an array, (2) sort the array in decreasing order by some simple algorithm (such as bubblesort), (3) return the element in position k. Solution 2: (1) read the first k elements into an array and sort them in decreasing order, (2) each remaining element is read one by one, (2.1) If it is smaller than the kth element in the array, it is ignored; (2.2) Otherwise, it is placed in its correct spot in the array, bumping one element out of the array. (3) the element in the kth position is returned as the answer
    Which solution is better when (1) N ~ k (2) N » k ? 答案： 1.O(N） 2.O(N^2) 3.O(N^3) 4.O(N^2) 5.O(N^2) 6.O(N^4) 冒泡排序法的复杂度：O(N^2 ); 第一种算法：全排，复杂度为 O(N^2); 第二种算法：前 k 个元素全排复杂度为 O(k^2)，剩余(N-k)个数依次读入的复杂度为(N-k)*k, 即复杂度为 O(k^2+(N-k)*k); 分情况讨论： ①当 N 与 k 十分接近的时候，N-k 可以近似为 0，复杂度就是 k^2 ≈N^2 ； ②当 N 远远大于>>k 的时候，k^2 可以近似为 0，N-k 近似为 N，所以复杂度近似为 O(N);
    分享到：
    赞 收藏

    相关推荐

    资料库

    课程资源

    共收录17145份资料，累计13个分类，关注成员有19位，主要包括：PHP,网络管理,网页制作,Java,.Net,数据库,3G/移动开发,C/C++,游戏开发,嵌入式,讲义,软件测试,专业指导

    热门标签

    PHP 网络管理 网页制作 Java .Net 数据库 3G/移动开发 C/C++ 游戏开发 嵌入式 讲义 软件测试 专业指导

    最新资料