Змаговий аналіз (онлайн алгоритм)

Змаговий аналіз — це метод для аналізу онлайн алгоритмів, в якому швидкодія онлайн алгоритму (який працює з непередбачною послідовністю запитів, опрацьовуючи кожен запит не бачачи майбутнього) порівнюється зі швидкодією оптимального офлайн алгоритму, який може бачити послідовність запитів заздалегідь. Кажуть, що алгоритм змаговий, якщо його співвідношення змаговості — співвідношення між його швидкодією і швидкодією офлайн алгоритму — обмежене. На відміну від традиційного аналізу найгіршого випадку^[en], де швидкодія алгоритму виміряється лише для «складних» входів, змаговий аналіз вимагає, щоб алгоритм однаково добре поводився як на легких так і на складних входах, де «легкість» і «складність» визначені швидкодією оптимального офлайн алгоритму.

Для багатьох алгоритмів, швидкодія залежить не тільки від розміру входів, але й від їхніх значень. Наприклад, складність сортування масиву різниться залежно від початкового порядку елементів. Такі залежні від даних алгоритми аналізують для середнього випадку і для найгіршого випадку. Змаговий аналіз це спосіб виконання аналізу найгіршого випадку для онлайн і увипадковлених алгоритмів, які зазвичай залежні від даних.

У змаговому аналізі, ми уявляємо «суперника», який навмисно обирає складні дані, щоб унайбільшити співвідношення ціни між алгоритмом, що ми його розглядаємо, і деяким оптимальним алгоритмом. Розглядаючи увипадковлений алгоритм, ми мусимо далі розрізняти між неуважним суперником, який не знає про випадкові вибори, які робить алгоритм проти якого він змагається, і пристосовним суперником, який має повне знання про внутрішній стан алгоритму в будь-яку мить під час виконання. (Для детермінованого алгоритму різниці немає; будь-який з противників може просто обчислити, який стан повинен мати цей алгоритм у будь-який час у майбутньому і відповідно вибрати складні дані.)

Read other articles:

Cyonosaurus

CyonosaurusRentang fosil: Permian Akhir Restorasi Cyonosaurus longiceps Klasifikasi ilmiah Kerajaan: Animalia Filum: Chordata (tanpa takson): Klad SynapsidaKlad TherapsidaKlad †Gorgonopsia Genus: †CyonosaurusOlsen, 1937 Spesies tipe †Cyonosaurus longicepsOlsen, 1937 Spesies lain †C. rubidgei (Broom, 1937 [awalnya Cyniscops rubidgei]) †C. kitchingi (Broom, 1936 [awalnya Galerhynchus kitchingi]) †C. broomianus (von Huene, 1950 [awalnya Cyniscops broomianus]) †C. tenuirostris (Boo...

Desmopuntius

Desmopuntius Desmopuntius foerschi Klasifikasi ilmiah Domain: Eukaryota Kerajaan: Animalia Filum: Chordata Kelas: Actinopterygii Ordo: Cypriniformes Famili: Cyprinidae Subfamili: Barbinae Genus: DesmopuntiusKottelat, 2013 Spesies tipe Barbus hexazonaM. C. W. Weber & de Beaufort, 1912 Spesies Lihat teks Desmopuntius adalah genus kecil dalam keluarga ikan mas (Cyprinidae) yang berasal dari Asia Tenggara. Mereka sebelumnya termasuk dalam genus Puntius.[1] Etimologi Nama Desmopuntius...

Gerombolan Siberat

Gerombolan Siberat Dari kiri ke kanan: Burger, Baggy, Bouncer, Bigtime, Ma Beagle, Bugle, Bankjob, dan Babyface. Penampilan perdana Walt Disney's Comics and Stories issue 134 Pencipta Carl Barks Pengisi suara Frank Welker, Chuck McCann, Peter Cullen, Terry McGovern, Brian Cummings Informasi terkait Nama alias Saudara Binatang peliharaan Rekan Boris, Mimi Hitam Musuh Gerombolan Siberat adalah karakter fiksi Disney. Mereka adalah grup penjahat yang selalu berusaha merampok Gudang Uang milik Go...

1875 Wisconsin gubernatorial election

American election 1875 Wisconsin gubernatorial election ← 1873 November 2, 1875 1877 → Nominee Harrison Ludington William Robert Taylor Party Republican Democratic Alliance — Reform Popular vote 85,155 84,314 Percentage 50.07% 49.58% County resultsLudington : 50–60% 60–70% 70–80% 80–90% >90%Tay...

Kosmos 140

Soviet uncrewed flight of the Soyuz programme Kosmos 140Mission typeTest flightOperatorExperimental Design Bureau (OKB-1)COSPAR ID1967-009A SATCAT no.02667Mission duration2 days Spacecraft propertiesSpacecraftSoyuz 7K-OK No.3Spacecraft typeSoyuz 7K-OKManufacturerExperimental Design Bureau (OKB-1)Launch mass6450 kg[1]Landing mass2500 kgDimensions7.13 m (23.4 ft) long2.72 m (8 ft 11 in) wide Start of missionLaunch date7 February 1967, 03:21 GMT[2]RocketS...

Club Alianza Lima

Club Alianza LimaCalcio Aliancistas, Blanquiazules, Grones , Intimos, El Equipo del Pueblo Segni distintivi Uniformi di gara Casa Trasferta Colori sociali Bianco, blu Simboli Gallo nero Inno Arriba Alianza Lima Dati societari Città Lima Nazione Perù Confederazione CONMEBOL Federazione FPF Campionato Liga 1 Fondazione 1901 Rifondazione1928 Presidente Fernando Salazar Allenatore Mauricio Larriera Stadio Estadio Alejandro Villanueva(35 000 posti) Sito web www.clubalianzalima.com Pa...

China Radio International

State radio broadcaster in China Radio Beijing redirects here. For the municipal radio station (Radio Beijing Corporation), see Beijing Renmin Guangbo Diantai. CRI headquartersTypeState mediaCountryChinaFounded3 December 1941HeadquartersBeijing, ChinaBroadcast areaWorldwideOwnerPropaganda Department of the Chinese Communist PartyParentChina Media GroupFormer names Radio Peking Radio Beijing Official websitewww.cri.cn China Radio InternationalSimplified Chinese中国国际广播电台Tradition...

Zamora-Chinchipe Province

Province of Ecuador This article needs additional citations for verification. Please help improve this article by adding citations to reliable sources. Unsourced material may be challenged and removed.Find sources: Zamora-Chinchipe Province – news · newspapers · books · scholar · JSTOR (July 2009) (Learn how and when to remove this message) Province in EcuadorZamora ChinchipeProvinceProvince of Zamora ChinchipeA picture of the Mayo River as it flows th...

美国众议院

此條目需要补充更多来源。 (2021年7月4日)请协助補充多方面可靠来源以改善这篇条目，无法查证的内容可能會因為异议提出而被移除。致使用者：请搜索一下条目的标题（来源搜索：美国众议院 — 网页、新闻、书籍、学术、图像），以检查网络上是否存在该主题的更多可靠来源（判定指引）。美國眾議院 United States House of Representatives第118届美国国会众议院徽章众议院旗...

Bootstrapping

Self-starting process that is supposed to proceed without external input For other uses, see Bootstrapping (disambiguation). In general, bootstrapping usually refers to a self-starting process that is supposed to continue or grow without external input. Etymology A pair of boots with one bootstrap visible Tall boots may have a tab, loop or handle at the top known as a bootstrap, allowing one to use fingers or a boot hook tool to help pull the boots on. The saying to pull oneself up by one's b...

Nankhatai

South Asian baked good NankhataiAlternative namesKulcha-e-KhatayeTypeShortbreadAssociated cuisineIndian, Bangladeshi, PakistaniMain ingredientsWheat flour, Rice flour, Butter, Powdered Sugar, Milk/Yogurt, Salt, Honey, Baking Powder Media: Nankhatai Nankhatai (Bengali: নানখাতাই, Hindustani: नानख़टाई (Devanagari) / نان خطائی (Urdu)/ Ghanakatha (Sinhala)) are shortbread biscuits originating from the Gujarat region of the Indian subcontinent, popu...

Deep Space Homer

«Deep Space Homer» Episodio de Los SimpsonEpisodio n.º Temporada 5Episodio 15Código de producción 1F13Guionista(s) David MirkinDirector Carlos BaezaEstrellas invitadas Buzz Aldrin como sí mismoJames Taylor como sí mismoFecha de emisión original 24 de febrero de 1994 en EE. UU.Gag del sofá La familia corre al sillón, pero hay un hombre obeso sentado en él. Este se corre al costado, dejándoles muy poco lugar.[1] Cronología «Lisa vs. Malibu Stacy» �...

Luxembourg at the Olympics

Sporting event delegationLuxembourg at theOlympicsIOC codeLUXNOCLuxembourg Olympic and Sporting CommitteeWebsitewww.teamletzebuerg.lu (in French)MedalsRanked 91st Gold 2 Silver 3 Bronze 0 Total 5 Summer appearances19001904–190819121920192419281932193619481952195619601964196819721976198019841988199219962000200420082012201620202024Winter appearances1928193219361948–19841988199219941998200220062010201420182022 Luxembourg's National Olympic Committee, the Luxembourg Olympic and Sporting ...

Growing Up (album IU)

Growing UpAlbum studio karya IUDirilis23 April 2009Direkam2009LOEN Studio, Seoul, Korea SelatanBooming Studio, Seoul, Korea SelatanVitamin Studio, Seoul, South KoreaKnuckles Korea Studio, Seoul, Korea SelatanGenreK-popDurasi56:21LabelLOEN EntertainmentProduserChoi Kab Won chongKronologi IU Lost and Found(2008)Lost and Found2008 Growing Up(2009) IU...IM(2009)IU...IM2009 Singel dalam album Growing Up BooDirilis: 23 April 2009 You Know (Rock Ver.)Dirilis: 30 Juni 2009 Templat:Korean membutuh...

Roger-Yves Bost

Questa voce sull'argomento cavallerizzi francesi è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Roger-Yves BostNazionalità Francia Altezza176 cm Peso80 kg Equitazione Palmarès Competizione Ori Argenti Bronzi Olimpiadi 1 0 0 Mondiali 1 2 0 Europei 1 0 1 Vedi maggiori dettagli Modifica dati su Wikidata · Manuale Roger-Yves Bost (Boulogne-Billancourt, 21 ottobre 1965) è un cavaliere francese. Indice 1 Palmarès 1.1 Olimpiadi 1.2 Mond...

Michael Brisker

Questa voce sull'argomento cestisti israeliani è solo un abbozzo. Contribuisci a migliorarla secondo le convenzioni di Wikipedia. Segui i suggerimenti del progetto di riferimento. Michael BriskerNazionalità Israele Altezza185 cm Peso80 kg Pallacanestro RuoloGuardia Squadra Ironi Kiryat Ata CarrieraGiovanili Maccabi Ra'anana Squadre di club 2016-2017 Maccabi Ra'anana2017-2019 Hapoel Eilat0 (0)2017-2019→ Maccabi Ra'anana2019-2020 Hapoel Tel Aviv8 (...

Saccharomyces cerevisiae

Ada usul agar Saccharomyces sp digabungkan ke artikel ini. (Diskusikan) Diusulkan sejak Februari 2022. artikel ini perlu dirapikan agar memenuhi standar Wikipedia. Tidak ada alasan yang diberikan. Silakan kembangkan artikel ini semampu Anda. Merapikan artikel dapat dilakukan dengan wikifikasi atau membagi artikel ke paragraf-paragraf. Jika sudah dirapikan, silakan hapus templat ini. (Pelajari cara dan kapan saatnya untuk menghapus pesan templat ini) Saccharomyces cerevisiae S. cerevisiae dili...

Rape of Belgium

Systematic war crimes against Belgian civilians during World War I Not to be confused with Rape in Belgium. Rape of BelgiumPart of the German occupation of Belgium during World War IThe execution of the notables of Blégny, 1914 by Belgian painter Évariste CarpentierLocationBelgiumDate4 August 1914 (1914-08-04) – 23 November 1918 (1918-11-23)TargetBelgian civiliansAttack typeWar crime, mass murder, forced labourDeathsAt least 23,700 killedInjured33,100Vic...

Troll (Internet)

Pour les articles homonymes, voir Troll et Troll (homonymie). Imagerie typique associée au troll sur Internet, un perturbateur qui se cache derrière son ordinateur pour diffuser des controverses artificielles, notamment sur les réseaux sociaux. En argot Internet, un troll caractérise un individu cherchant l'attention par la création de ressentis négatifs, ou un comportement qui vise à générer des polémiques. Il peut s'agir d'un message (par exemple sur un forum), d'un débat confli...

UFC 213

UFC 213: Romero vs. WhittakerProdotto daUltimate Fighting Championship Data8 luglio 2017 Città Paradise, Stati Uniti SedeT-Mobile Arena Spettatori12 834[1] Cronologia pay-per-viewThe Ultimate Fighter: Redemption FinaleUFC 213: Romero vs. WhittakerUFC Fight Night: Nelson vs. Ponzinibbio Progetto Wrestling Manuale UFC 213: Romero vs. Whittaker è stato un evento di arti marziali miste tenuto dalla Ultimate Fighting Championship l'8 luglio 2017 alla T-Mobile Arena di Paradise, negl...