時間と空間のトレードオフ

曖昧さ回避 この項目では、計算機科学における時間と空間のトレードオフについて説明しています。一般的なトレードオフについては「トレードオフ」をご覧ください。

計算機科学における時間と空間のトレードオフ（じかんとくうかんのトレードオフ、英: space-time tradeoff）または時間と記憶域のトレードオフ（じかんときおくいきのトレードオフ、英: time-memory tradeoff、タイム・メモリ・トレードオフ）とは、メモリの使用量が削減できる代わりにプログラムの速度が低下する、または逆に、計算にかかる時間を削減できる代わりにメモリの使用量が増える、という状況のことを言う。

時間と空間がトレードオフの関係にある場合、最適な選択は、CPUの速度、RAMの量、ハードディスクの容量の価格比によって大きく異なる。しばしば、時間と空間のトレードオフを利用して、問題の複雑性クラスを変えるというテクニックも使用される。

時間と空間のトレードオフの例として最も一般的なのはルックアップテーブルを利用したアルゴリズムである。テーブルの全てを最初から持つようにした実装では、処理時間は削減できるが、必要なメモリの量は増加する。また、テーブルの要素をその都度計算することもでき、これは計算時間は増加するが、必要なメモリの量を削減できる。

時間と空間のトレードオフは、データストレージにも当てはまる。データを圧縮せずに保存すると、圧縮した場合と比べ、消費する容量は多く、必要な時間は短くなる。データの圧縮によって保存に必要な領域を減らすことができるが、データ圧縮処理を行う時間が必要になる。どちらが適切かは場合によって異なる。

もう一つの例として、数式をウィキペディアで表示する方法が挙げられる。LaTeXのソースだけを保存しておき、ページを表示する度にそれをレンダリングする方法をとれば、時間はかかるが、記憶装置の使用量は少なくて済み、空間を時間でまかなうことができる。ページが保存されたときに画像をレンダリングし、それを保存しておく方法をとれば、記憶装置の使用量は多くなるが、時間は短くて済み、時間を空間でまかなうことができる。

時間と空間のトレードオフを利用して実行時間を短くしているアルゴリズムとして、離散対数の計算で利用されるベビーステップジャイアントステップ（英語版）アルゴリズムがある。

他の分野では、暗号システムに対する総当たり攻撃におけるレインボーテーブルの作成が、時間と空間のトレードオフにあたる。中間一致攻撃も時間と空間のトレードオフの応用である。

外部リンク

スタブアイコン

この項目は、コンピュータに関連した書きかけの項目です。この項目を加筆・訂正などしてくださる協力者を求めています（PJ:コンピュータ/P:コンピュータ）。

Read other articles:

Eparki San Diego

Eparki Eparki Katolik Kaldea Santo Petrus RasulEparchia Sancti Petri Apostoli urbis Sancti Didaci ChaldaeorumKatolik LokasiNegaraAmerika SerikatWilayahAmerika Serikat BaratProvinsi gerejawiSubyek langsung Tahta SuciInformasiDenominasiKatolikGereja sui iurisGereja Katolik KaldeaRitusRitus KaldeaPendirian21 Mei 2002KatedralKatedral Santo PetrusKepemimpinan kiniPausFransiskusPatriarkLouis Raphaël I SakoUskupEmanuel Hana ShaletaSitus webhttp://www.kaldu.org Eparki Santo Petrus Rasul (Latin:...

 

Ictaluridae

IctaluridaeRentang fosil: Eosen - sekarang PreЄ Є O S D C P T J K Pg N Ictalurus punctatus Klasifikasi ilmiah Domain: Eukaryota Kerajaan: Animalia Filum: Chordata Kelas: Actinopterygii Ordo: Siluriformes Superfamili: Ictaluroidea Famili: IctaluridaeT. N. Gill, 1861 Genus Ameiurus Astephus (punah) Ictalurus Noturus Prietella Pylodictis Satan Trogloglanis Ictaluridae adalah keluarga ikan berkumis asli Amerika Utara, di mana mereka merupakan sumber makanan penting dan terkadang dipancing untu...

 

Yesaya 23

Yesaya 23Gulungan Besar Kitab Yesaya, yang memuat lengkap seluruh Kitab Yesaya, dibuat pada abad ke-2 SM, diketemukan di gua 1, Qumran, pada tahun 1947.KitabKitab YesayaKategoriNevi'imBagian Alkitab KristenPerjanjian LamaUrutan dalamKitab Kristen23← pasal 22 pasal 24 → Yesaya 23 (disingkat Yes 23) adalah bagian dari Kitab Yesaya dalam Alkitab Ibrani dan Perjanjian Lama di Alkitab Kristen.[1] Memuat Firman Allah yang disampaikan oleh nabi Yesaya bin Amos terutama berkenaan ...

Strada statale 483 Termolese

Strada statale 483TermoleseLocalizzazioneStato Italia Regioni Molise Province Campobasso DatiClassificazioneStrada statale InizioPalata FineTermoli Lunghezza31,825[1] km Provvedimento di istituzioneD.M. 22/12/1964 - G.U. 48 del 24/02/1965[2] GestoreTratte ANAS: nessuna (dal 2001 la gestione è passata alla Provincia di Campobasso) Percorso Manuale La ex strada statale 483 Termolese (SS 483), ora strada provinciale 168 Termolese (SP 168)[3], è una strada...

 

The Times of Israel

Israel-based online newspaper The Times of IsraelHead office in Jerusalem (2012)TypeOnline newspaperFounder(s)David HorovitzSeth KlarmanEditor-in-chiefDavid HorovitzEditorSuha Halifa (Arabic)Stephanie Bitan (French)Avi Davidi (Persian)Deputy editorJoshua DavidovichElie LeshemAmanda Borschel-DanOpinion editorMiriam HerschlagLaunchedFebruary 2012; 12 years ago (2012-02)Political alignmentCentre[1][2][3][4][5][6][7]La...

 

Piala Liga Inggris 2012–2013

Piala Liga Inggris 2012–20132012–13 Football League CupNegara Inggris WalesTanggal penyelenggaraan11 Agustus 2012 s.d. 24 Februari 2013Jumlah peserta92Juara bertahanLiverpoolJuaraSwansea City(gelar ke-1)Tempat keduaBradford CityJumlah pertandingan91Jumlah gol321 (3.53 per pertandingan)Pencetak gol terbanyakTheo Walcott(5 gol)[1]← 2011–2012 2013–2014 → Piala Liga Inggris 2012–2013 adalah edisi ke-53 penyelenggaraan Piala Liga Inggris, sebuah kompetisi dengan sis...

Bærum

Lambang Bærum Bærum adalah kotamadya di Akershus, Norwegia. Kotamadya ini memiliki 104.690 penduduk pada Januari 2005. Penduduk tuanya berjumlah (67 tahun ke atas) 13,4%. Pada Juni 2005 pengangguran mencapai 2,2%. Ibu kota kotamadya ini ada di Sandvika Sumber Biro Statistik Norwegia

 

1900 Florida gubernatorial election

For related races, see 1900 United States gubernatorial elections. 1900 Florida gubernatorial election ← 1896 November 6, 1900 1904 →   Nominee William Sherman Jennings Matthew B. MacFarlane Party Democratic Republican Popular vote 29,251 6,238 Percentage 80.98% 17.27% County Results Congressional District Result Jennings  50–60%  60–70%  70–80%  80–90%  >90% Governor before election William D. ...

 

Maude (serie televisiva)

Questa voce o sezione sull'argomento sitcom non cita le fonti necessarie o quelle presenti sono insufficienti. Puoi migliorare questa voce aggiungendo citazioni da fonti attendibili secondo le linee guida sull'uso delle fonti. MaudeTitolo originaleMaude PaeseStati Uniti d'America Anno1972-1978 Formatoserie TV Generesitcom Stagioni6 Episodi141 Durata30 min Lingua originaleinglese Rapporto4:3 CreditiIdeatoreNorman Lear Interpreti e personaggi Beatrice Arthur: Maude Findlay Bill Macy: Walt...

Al di là del mistero

Al di là del misteroGlenn Strange (nei panni del mostro di Frankenstein) trascina Boris KarloffTitolo originaleThe House of Frankenstein Paese di produzioneStati Uniti d'America Anno1944 Durata71 min Dati tecniciB/N Genereorrore RegiaErle C. Kenton SoggettoCurt Siodmak ProduttorePaul Malvern FotografiaGeorge Robinson MontaggioPhilip Cahn Effetti specialiJohn P. FultonCarl Elmendorf TruccoJack Pierce Interpreti e personaggi Boris Karloff: Dr. Gustav Niemann Lon Chaney Jr.: Lawrence Talbot Joh...

 

José Mauri

Artikel ini sebatang kara, artinya tidak ada artikel lain yang memiliki pranala balik ke halaman ini.Bantulah menambah pranala ke artikel ini dari artikel yang berhubungan atau coba peralatan pencari pranala.Tag ini diberikan pada November 2022. José Agustín MauriInformasi pribadiTanggal lahir 6 April 1996 (umur 28)Tempat lahir Realicó, ArgentinaTinggi 1,69 m (5 ft 7 in)Posisi bermain GelandangInformasi klubKlub saat ini ParmaNomor 26Karier junior-2013 ParmaKarier senio...

 

Italian aircraft carrier Cavour

Italian aircraft carrier Cavour History Italy NameCavour[1] NamesakeCamillo Benso, conte di Cavour Ordered22 November 2000 BuilderFincantieri Cost€1.39 billion (2010) Laid down17 July 2001 Launched20 July 2004 Commissioned27 March 2008 In service10 June 2009 HomeportTaranto IdentificationPennant number: 550 MottoIn arduis servare mentem StatusActive General characteristics TypeAircraft carrier Displacement27,100 metric tons (26,700 long tons)[2] (30,000 MT full load)[3&#...

Philco computers

Computer series Philco was one of the pioneers of transistorized computers. After the company developed the surface barrier transistor, which was much faster than previous point-contact types, it was awarded contracts for military and government computers. Commercialized derivatives of some of these designs became successful business and scientific computers. The TRANSAC (Transistor Automatic Computer) Model S-1000 was released as a scientific computer. The TRANSAC S-2000 mainframe computer s...

 

Mario Gomboli

Mario Gomboli nel 2009 Mario Giuseppe Gomboli (Brescia, 18 luglio 1947) è un fumettista, sceneggiatore e illustratore italiano, noto soprattutto come soggettista e direttore responsabile, nonché editore, della serie Diabolik[1][2][3]. Biografia Nato a Brescia, quando è ancora bambino la famiglia si trasferisce a Milano dove, quando è studente al Liceo Scientifico Statale “Alessandro Volta”, conosce un compagno di classe, Alfredo Castelli, con il quale collabora...

 

Icon

Religious work of art in Christianity This article is about religious images. For pictograms used in graphical user interfaces, see Icon (computing). For other uses, see Icon (disambiguation). The Ladder of Divine Ascent depicts monks ascending to Jesus in heaven in the top right. 12th century, Saint Catherine's Monastery. Part of a series on theEastern Orthodox ChurchMosaic of Christ Pantocrator, Hagia Sophia Overview Structure Theology (History of theology) Liturgy Church history Holy ...

2014–15 Elon Phoenix men's basketball team

American college basketball season 2014–15 Elon Phoenix men's basketballConferenceColonial Athletic AssociationRecord15–18 (6–12 CAA)Head coachMatt Matheny (6th season)Assistant coaches Jack Wooten Monty Sanders Chris Long Home arenaAlumni GymSeasons← 2013–142015–16 → 2014–15 CAA men's basketball standings vte Conf Overall Team W   L   PCT W   L   PCT William & Mary 12 – 6   .667 20 – 13   .606 UNC Wilmi...

 

Premier hôpital de la ville de Belgrade

Cet article est une ébauche concernant un monument culturel serbe. Vous pouvez partager vos connaissances en l’améliorant (comment ?) selon les recommandations des projets correspondants. Premier hôpital de la villeПрва варошка болницаPrva varoška bolnicaLe premier hôpital de la ville de BelgradePrésentationDestination initiale HôpitalStyle NéoromantismeArchitecte Jovan FrenclConstruction 1868Patrimonialité Bien culturel de la Ville de BelgradeLocalisationPa...

 

Olbia Calcio 1905 2020-2021

Voce principale: Olbia Calcio 1905. Olbia Calcio 1905Stagione 2020-2021Sport calcio Squadra Olbia Allenatore Massimiliano Canzi All. in seconda Luigi Lavecchia Presidente Alessandro Marino Serie C13° Maggiori presenzeCampionato: Altare (35) Miglior marcatoreCampionato: Ragatzu (13) StadioBruno Nespoli (4.000) 2019-2020 2021-2022 Dati aggiornati al 18 aprile 2021Si invita a seguire il modello di voce Questa voce raccoglie le informazioni riguardanti l'Olbia Calcio 1905 nelle competi...

WKLG

Radio station in Rock Harbor, FloridaWKLGRock Harbor, FloridaBroadcast areaFlorida Keys areaFrequency102.1 MHzBrandingStar 102.1ProgrammingFormatAdult contemporaryOwnershipOwnerWKLG, Inc.HistoryCall sign meaningKey LarGoTechnical information[1]Licensing authorityFCCFacility ID73177ClassC1ERP100,000 wattsHAAT131 metersTransmitter coordinates25°5′29.00″N 80°26′37.00″W / 25.0913889°N 80.4436111°W / 25.0913889; -80.4436111LinksPublic license information...

 

Civil Code of Russia

Prime source of civil law for Russia Civil Code of RussiaParliament of RussiaTerritorial extentRussiaEnacted byParliament of RussiaSigned byPresident of RussiaSigned1994Commenced1 January 1995Status: In force The Civil Code of the Russian Federation (‹See Tfd›Russian: Гражданский кодекс Российской Федерации, frequently abbreviated 'ГК РФ') is the prime source of civil law for the Russian Federation. The Russian Civil Law system descended f...