主頁 > .NET開發 > 如果我們知道有回傳陣列中位數的O(n)函式，如何在O(n)處找到第k個最小元素

如果我們知道有回傳陣列中位數的O(n)函式，如何在O(n)處找到第k個最小元素

2022-06-05 23:05:04 .NET開發

我正在嘗試找到一種演算法，該演算法通過使用在 O(n) 處回傳大小為 n 的陣列的中值的函式，在 O(n) 處從大小為 n 的未排序陣列中找到第 k 個最小元素。我想我必須找到一個時間復雜度像cn cn/2 cn/2^2 .... cn/2^j=O(n)的遞回函式。

uj5u.com熱心網友回復：

您可以使用提供的 O(n) 中值查找演算法來使用快速選擇。

在 O(n) 時間內找到中位數，將陣列分成三部分（小于、等于和大于中位數），然后遞回到相關部分。

復雜性分析很容易（與標準隨機快速選擇演算法相比）。找到中位數和旋轉陣列都是 O(n)，然后一個遞回到的陣列的大小最多有 n/2 個元素（根據中位數的定義）。所以遞回關系是 T(n) = n T(n/2)，其解是 T(n) = O(n)。

轉載請註明出處，本文鏈接：https://www.uj5u.com/net/485807.html

標籤：算法 中位数 中位数的中位数

上一篇：實作素數散列的最佳方法是什么？

下一篇：重新平衡陣列中的資料以生成所有相同的值

標籤雲
其他(157675) Python(38076) JavaScript(25376) Java(17977) C(15215) 區塊鏈(8255) C＃(7972) AI(7469) 爪哇(7425) MySQL(7132) html(6777) 基礎類(6313) sql(6102) 熊猫(6058) PHP(5869) 数组(5741) R(5409) Linux(5327) 反应(5209) 腳本語言(PerlPython)(5129) 非技術區(4971) Android(4554) 数据框(4311) css(4259) 节点.js(4032) C語言(3288) json(3245) 列表(3129) 扑(3119) C++語言(3117) 安卓(2998) 打字稿(2995) VBA(2789) Java相關(2746) 疑難問題(2699) 细绳(2522) 單片機工控(2479) iOS(2429) ASP.NET(2402) MongoDB(2323) 麻木的(2285) 正则表达式(2254) 字典(2211) 循环(2198) 迅速(2185) 擅长(2169) 镖(2155) 功能(1967) .NET技术(1958) Web開發(1951) python-3.x(1918) HtmlCss(1915) 弹簧靴(1913) C++(1909) xml(1889) PostgreSQL(1872) .NETCore(1853) 谷歌表格(1846) Unity3D(1843) for循环(1842)

熱門瀏覽
  • WebAPI簡介

    Web體系結構： 有三個核心：資源(resource)，URL(統一資源識別符號)和表示 他們的關系是這樣的：一個資源由一個URL進行標識，HTTP客戶端使用URL定位資源，表示是從資源回傳資料，媒體型別是資源回傳的資料格式。 接下來我們說下HTTP. HTTP協議的系統是一種無狀態的方式，使用請求/ ......

    uj5u.com 2020-09-09 22:07:47 more
  • asp.net core 3.1 入口：Program.cs中的Main函式

    本文分析Program.cs 中Main()函式中代碼的運行順序分析asp.net core程式的啟動，重點不是剖析原始碼，而是理清程式開始時執行的順序。到呼叫了哪些實體，哪些法方。asp.net core 3.1 的程式入口在專案Program.cs檔案里，如下。ususing System; us ......

    uj5u.com 2020-09-09 22:07:49 more
  • asp.net網站作為websocket服務端的應用該如何寫

    最近被websocket的一個問題困擾了很久，有一個需求是在web網站中搭建websocket服務。客戶端通過網頁與服務器建立連接，然后服務器根據ip給客戶端網頁發送資訊。 其實，這個需求并不難，只是剛開始對websocket的內容不太了解。上網搜索了一下，有通過asp.net core 實作的、有 ......

    uj5u.com 2020-09-09 22:08:02 more
  • ASP.NET 開源匯入匯出庫Magicodes.IE Docker中使用

    Magicodes.IE在Docker中使用 更新歷史 2019.02.13 【Nuget】版本更新到2.0.2 【匯入】修復單列匯入的Bug，單元測驗“OneColumnImporter_Test”。問題見（https://github.com/dotnetcore/Magicodes.IE/is ......

    uj5u.com 2020-09-09 22:08:05 more
  • 在webform中使用ajax

    如果你用過Asp.net webform， 說明你也算是.NET 開發的老兵了。WEBform應該是2011 2013左右，當時還用visual studio 2005、 visual studio 2008。后來基本都用的是MVC。 如果是新開發的專案，估計沒人會用webform技術。但是有些舊版 ......

    uj5u.com 2020-09-09 22:08:50 more
  • iis添加asp.net網站，訪問提示：由于擴展配置問題而無法提供您請求的

    今天在iis服務器配置asp.net網站，遇到一個問題，記錄一下： 問題：由于擴展配置問題而無法提供您請求的頁面。如果該頁面是腳本，請添加處理程式。如果應下載檔案，請添加 MIME 映射。 WindowServer2012服務器，添加角色安裝完.netframework和iis之后，運行aspx頁面 ......

    uj5u.com 2020-09-09 22:10:00 more
  • WebAPI-處理架構

    帶著問題去思考，大家好！ 問題1：HTTP請求和回傳相應的HTTP回應資訊之間發生了什么？ 1：首先是最底層，托管層，位于WebAPI和底層HTTP堆疊之間 2：其次是 訊息處理程式管道層，這里比如日志和快取。OWIN的參考是將訊息處理程式管道的一些功能下移到堆疊下端的OWIN中間件了。 3：控制器處理 ......

    uj5u.com 2020-09-09 22:11:13 more
  • 微信門戶開發框架-使用指導說明書

    微信門戶應用管理系統，采用基于 MVC + Bootstrap + Ajax + Enterprise Library的技術路線，界面層采用Boostrap + Metronic組合的前端框架，資料訪問層支持Oracle、SQLServer、MySQL、PostgreSQL等資料庫。框架以MVC5，... ......

    uj5u.com 2020-09-09 22:15:18 more
  • WebAPI-HTTP編程模型

    帶著問題去思考，大家好！它是什么？它包含什么？它能干什么？ 訊息 HTTP編程模型的核心就是訊息抽象，表示為：HttPRequestMessage,HttpResponseMessage.用于客戶端和服務端之間交換請求和回應訊息。 HttpMethod類包含了一組靜態屬性： private stat ......

    uj5u.com 2020-09-09 22:15:23 more
  • 部署WebApi隨筆

    一、跨域 NuGet參考Microsoft.AspNet.WebApi.Cors WebApiConfig.cs中配置： // Web API 配置和服務 config.EnableCors(new EnableCorsAttribute("*", "*", "*")); 二、清除默認回傳XML格式 ......

    uj5u.com 2020-09-09 22:15:48 more
最新发布
  • C#多執行緒學習(二) 如何操縱一個執行緒

    <a href="https://www.cnblogs.com/x-zhi/" target="_blank"><img width="48" height="48" class="pfs" src="https://pic.cnblogs.com/face/2943582/20220801082530.png" alt="" /></...

    uj5u.com 2023-04-19 09:17:20 more
  • C#多執行緒學習(二) 如何操縱一個執行緒

    C#多執行緒學習(二) 如何操縱一個執行緒 執行緒學習第一篇：C#多執行緒學習(一) 多執行緒的相關概念 下面我們就動手來創建一個執行緒，使用Thread類創建執行緒時，只需提供執行緒入口即可。（執行緒入口使程式知道該讓這個執行緒干什么事） 在C#中，執行緒入口是通過ThreadStart代理（delegate）來提供的 ......

    uj5u.com 2023-04-19 09:16:49 more
  • 記一次 .NET某醫療器械清洗系統 卡死分析

    <a href="https://www.cnblogs.com/huangxincheng/" target="_blank"><img width="48" height="48" class="pfs" src="https://pic.cnblogs.com/face/214741/20200614104537.png" alt="" /&g...

    uj5u.com 2023-04-18 08:39:04 more
  • 記一次 .NET某醫療器械清洗系統 卡死分析

    一：背景 1. 講故事 前段時間協助訓練營里的一位朋友分析了一個程式卡死的問題，回過頭來看這個案例比較經典，這篇稍微整理一下供后來者少踩坑吧。 二：WinDbg 分析 1. 為什么會卡死 因為是表單程式，理所當然就是看主執行緒此時正在做什么? 可以用 ~0s ; k 看一下便知。 0:000> k # ......

    uj5u.com 2023-04-18 08:33:10 more
  • SignalR, No Connection with that ID，IIS

    <a href="https://www.cnblogs.com/smartstar/" target="_blank"><img width="48" height="48" class="pfs" src="https://pic.cnblogs.com/face/u36196.jpg" alt="" /></a>...

    uj5u.com 2023-03-30 17:21:52 more
  • 一次對pool的誤用導致的.net頻繁gc的診斷分析

    <a href="https://www.cnblogs.com/dotnet-diagnostic/" target="_blank"><img width="48" height="48" class="pfs" src="https://pic.cnblogs.com/face/3115652/20230225090434.png" alt=""...

    uj5u.com 2023-03-28 10:15:33 more
  • 一次對pool的誤用導致的.net頻繁gc的診斷分析

    <a href="https://www.cnblogs.com/dotnet-diagnostic/" target="_blank"><img width="48" height="48" class="pfs" src="https://pic.cnblogs.com/face/3115652/20230225090434.png" alt=""...

    uj5u.com 2023-03-28 10:13:31 more
  • C#遍歷指定檔案夾中所有檔案的3種方法

    <a href="https://www.cnblogs.com/xbhp/" target="_blank"><img width="48" height="48" class="pfs" src="https://pic.cnblogs.com/face/957602/20230310105611.png" alt="" /></a&...

    uj5u.com 2023-03-27 14:46:55 more
  • C#/VB.NET：如何將PDF轉為PDF/A

    <a href="https://www.cnblogs.com/Carina-baby/" target="_blank"><img width="48" height="48" class="pfs" src="https://pic.cnblogs.com/face/2859233/20220427162558.png" alt="" />...

    uj5u.com 2023-03-27 14:46:35 more
  • 武裝你的WEBAPI-OData聚合查詢

    <a href="https://www.cnblogs.com/podolski/" target="_blank"><img width="48" height="48" class="pfs" src="https://pic.cnblogs.com/face/616093/20140323000327.png" alt="" /><...

    uj5u.com 2023-03-27 14:46:16 more

Copyright © 2010-2020 有解無憂