mirror of
https://github.com/krahets/hello-algo.git
synced 2026-11-04 22:54:17 +08:00
2078 lines
71 KiB
HTML
2078 lines
71 KiB
HTML
|
||
<!DOCTYPE html>
|
||
|
||
<html class="no-js" lang="en">
|
||
<head>
|
||
<meta charset="utf-8"/>
|
||
<meta content="width=device-width,initial-scale=1" name="viewport"/>
|
||
<meta content="A data structures and algorithms tutorial with animated illustrations and code you can run with one click" name="description"/>
|
||
<meta content="krahets" name="author"/>
|
||
<link href="https://www.hello-algo.com/en/chapter_computational_complexity/summary/" rel="canonical"/>
|
||
<link href="../space_complexity/" rel="prev"/>
|
||
<link href="../exercises/" rel="next"/>
|
||
<link href="/chapter_computational_complexity/summary/" hreflang="zh" rel="alternate"/>
|
||
<link href="/zh-hant/chapter_computational_complexity/summary/" hreflang="zh-Hant" rel="alternate"/>
|
||
<link href="/en/chapter_computational_complexity/summary/" hreflang="en" rel="alternate"/>
|
||
<link href="/ja/chapter_computational_complexity/summary/" hreflang="ja" rel="alternate"/>
|
||
<link href="/ru/chapter_computational_complexity/summary/" hreflang="ru" rel="alternate"/>
|
||
<link href="/ko/chapter_computational_complexity/summary/" hreflang="ko" rel="alternate"/>
|
||
<link href="../../assets/images/favicon.png" rel="icon"/>
|
||
<meta content="zensical-0.0.51" name="generator"/>
|
||
<title>2.5 Summary - Hello Algo</title>
|
||
<link href="../../assets/stylesheets/modern/main.62c9b9cc.min.css" rel="stylesheet"/>
|
||
<link href="../../assets/stylesheets/modern/palette.dfe2e883.min.css" rel="stylesheet"/>
|
||
|
||
|
||
<style>:root{--md-text-font:"Noto Sans";--md-code-font:"JetBrains Mono"}</style>
|
||
<link href="../../stylesheets/extra.css" rel="stylesheet"/>
|
||
<link href="../../stylesheets/animation_player.css" rel="stylesheet"/>
|
||
<script>__md_scope=new URL("../..",location),__md_scope.pathname.endsWith("/")||(__md_scope=new URL(__md_scope.pathname+"/",location)),__md_hash=e=>[...e].reduce(((e,t)=>(e<<5)-e+t.charCodeAt(0)),0),__md_get=(e,t=localStorage,_=__md_scope)=>JSON.parse(t.getItem(_.pathname+"."+e)),__md_set=(e,t,_=localStorage,a=__md_scope)=>{try{_.setItem(a.pathname+"."+e,JSON.stringify(t))}catch(e){}},document.documentElement.setAttribute("data-platform",navigator.platform)</script>
|
||
<script data-ha-shared-palette="1">
|
||
/* Share only the palette across language roots; other preferences stay scoped. */
|
||
(() => {
|
||
const get = __md_get;
|
||
const set = __md_set;
|
||
const shared = new URL("/", location);
|
||
__md_get = (key, storage = localStorage, scope = __md_scope) => {
|
||
if (key !== "__palette") return get(key, storage, scope);
|
||
let value = get(key, storage, shared);
|
||
// Adopt the current language's old preference only if none is shared yet.
|
||
if (value === null && scope.pathname !== shared.pathname) {
|
||
value = get(key, storage, scope);
|
||
if (value !== null) set(key, value, storage, shared);
|
||
}
|
||
return value;
|
||
};
|
||
__md_set = (key, value, storage = localStorage, scope = __md_scope) =>
|
||
set(key, value, storage, key === "__palette" ? shared : scope);
|
||
})();
|
||
</script>
|
||
<link href="/assets/figure-svg/css/5632068fdac847e7b03f598e.css" rel="stylesheet"/></head>
|
||
<body data-md-color-accent="teal" data-md-color-primary="white" data-md-color-scheme="default" dir="ltr">
|
||
<input autocomplete="off" class="md-toggle" data-md-toggle="drawer" id="__drawer" type="checkbox"/>
|
||
<input autocomplete="off" class="md-toggle" data-md-toggle="search" id="__search" type="checkbox"/>
|
||
<label aria-label="Navigation" class="md-overlay" for="__drawer"></label>
|
||
<div data-md-component="skip">
|
||
<a class="md-skip" href="#25-summary">
|
||
Skip to content
|
||
</a>
|
||
</div>
|
||
<div data-md-component="announce">
|
||
<aside class="md-banner">
|
||
<div class="md-banner__inner md-grid md-typeset">
|
||
<div class="banner-svg">
|
||
<svg viewbox="0 0 512 512" xmlns="http://www.w3.org/2000/svg"><!--!Font Awesome Free 6.5.1 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free Copyright 2024 Fonticons, Inc.-->
|
||
<path d="M480 32c0-12.9-7.8-24.6-19.8-29.6s-25.7-2.2-34.9 6.9L381.7 53c-48 48-113.1 75-181 75H192 160 64c-35.3 0-64 28.7-64 64v96c0 35.3 28.7 64 64 64l0 128c0 17.7 14.3 32 32 32h64c17.7 0 32-14.3 32-32V352l8.7 0c67.9 0 133 27 181 75l43.6 43.6c9.2 9.2 22.9 11.9 34.9 6.9s19.8-16.6 19.8-29.6V300.4c18.6-8.8 32-32.5 32-60.4s-13.4-51.6-32-60.4V32zm-64 76.7V240 371.3C357.2 317.8 280.5 288 200.7 288H192V192h8.7c79.8 0 156.5-29.8 215.3-83.3z"></path>
|
||
</svg>
|
||
<span>Help improve the English edition. See our <a href="https://github.com/krahets/hello-algo/blob/main/en/CONTRIBUTING.md">contribution guidelines</a>.</span>
|
||
</div>
|
||
</div>
|
||
</aside>
|
||
</div>
|
||
<header class="md-header md-header--shadow" data-md-component="header">
|
||
<nav aria-label="Header" class="md-header__inner md-grid">
|
||
<a aria-label="Hello Algo" class="md-header__button md-logo" data-md-component="logo" href="../.." title="Hello Algo">
|
||
<img alt="Hello Algo" src="../../assets/images/logo.svg"/>
|
||
</a>
|
||
<label aria-label="Navigation" class="md-header__button md-icon" for="__drawer">
|
||
<svg class="lucide lucide-menu" fill="none" stroke="currentColor" stroke-linecap="round" stroke-linejoin="round" stroke-width="2" viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M4 5h16M4 12h16M4 19h16"></path></svg>
|
||
</label>
|
||
<div class="md-header__title" data-md-component="header-title">
|
||
<div class="md-header__ellipsis">
|
||
<div class="md-header__topic">
|
||
<span class="md-ellipsis">
|
||
Hello Algo
|
||
</span>
|
||
</div>
|
||
<div class="md-header__topic" data-md-component="header-topic">
|
||
<span class="md-ellipsis">
|
||
|
||
2.5 Summary
|
||
|
||
</span>
|
||
</div>
|
||
</div>
|
||
</div>
|
||
<form class="md-header__option" data-md-component="palette">
|
||
<input aria-label="Switch to dark mode" class="md-option" data-md-color-accent="teal" data-md-color-media="none" data-md-color-primary="white" data-md-color-scheme="default" id="__palette_0" name="__palette" type="radio"/>
|
||
<label class="md-header__button md-icon" for="__palette_1" hidden="" title="Switch to dark mode">
|
||
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M7.5 2c-1.79 1.15-3 3.18-3 5.5s1.21 4.35 3.03 5.5C4.46 13 2 10.54 2 7.5A5.5 5.5 0 0 1 7.5 2m11.57 1.5 1.43 1.43L4.93 20.5 3.5 19.07zm-6.18 2.43L11.41 5 9.97 6l.42-1.7L9 3.24l1.75-.12.58-1.65L12 3.1l1.73.03-1.35 1.13zm-3.3 3.61-1.16-.73-1.12.78.34-1.32-1.09-.83 1.36-.09.45-1.29.51 1.27 1.36.03-1.05.87zM19 13.5a5.5 5.5 0 0 1-5.5 5.5c-1.22 0-2.35-.4-3.26-1.07l7.69-7.69c.67.91 1.07 2.04 1.07 3.26m-4.4 6.58 2.77-1.15-.24 3.35zm4.33-2.7 1.15-2.77 2.2 2.54zm1.15-4.96-1.14-2.78 3.34.24zM9.63 18.93l2.77 1.15-2.53 2.19z"></path></svg>
|
||
</label>
|
||
<input aria-label="Switch to light mode" class="md-option" data-md-color-accent="teal" data-md-color-media="none" data-md-color-primary="black" data-md-color-scheme="slate" id="__palette_1" name="__palette" type="radio"/>
|
||
<label class="md-header__button md-icon" for="__palette_0" hidden="" title="Switch to light mode">
|
||
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M7.5 2c-1.79 1.15-3 3.18-3 5.5s1.21 4.35 3.03 5.5C4.46 13 2 10.54 2 7.5A5.5 5.5 0 0 1 7.5 2m11.57 1.5 1.43 1.43L4.93 20.5 3.5 19.07zm-6.18 2.43L11.41 5 9.97 6l.42-1.7L9 3.24l1.75-.12.58-1.65L12 3.1l1.73.03-1.35 1.13zm-3.3 3.61-1.16-.73-1.12.78.34-1.32-1.09-.83 1.36-.09.45-1.29.51 1.27 1.36.03-1.05.87zM19 13.5a5.5 5.5 0 0 1-5.5 5.5c-1.22 0-2.35-.4-3.26-1.07l7.69-7.69c.67.91 1.07 2.04 1.07 3.26m-4.4 6.58 2.77-1.15-.24 3.35zm4.33-2.7 1.15-2.77 2.2 2.54zm1.15-4.96-1.14-2.78 3.34.24zM9.63 18.93l2.77 1.15-2.53 2.19z"></path></svg>
|
||
</label>
|
||
</form>
|
||
<script>var palette=__md_get("__palette");if(palette&&palette.color){if("(prefers-color-scheme)"===palette.color.media){var media=matchMedia("(prefers-color-scheme: light)"),input=document.querySelector(media.matches?"[data-md-color-media='(prefers-color-scheme: light)']":"[data-md-color-media='(prefers-color-scheme: dark)']");palette.color.media=input.getAttribute("data-md-color-media"),palette.color.scheme=input.getAttribute("data-md-color-scheme"),palette.color.primary=input.getAttribute("data-md-color-primary"),palette.color.accent=input.getAttribute("data-md-color-accent")}for(var[key,value]of Object.entries(palette.color))document.body.setAttribute("data-md-color-"+key,value)}</script>
|
||
<div class="md-header__option">
|
||
<div class="md-select">
|
||
<button aria-label="Select language" class="md-header__button md-icon">
|
||
<svg class="lucide lucide-languages" fill="none" stroke="currentColor" stroke-linecap="round" stroke-linejoin="round" stroke-width="2" viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="m5 8 6 6M4 14l6-6 2-3M2 5h12M7 2h1M22 22l-5-10-5 10M14 18h6"></path></svg>
|
||
</button>
|
||
<div class="md-select__inner">
|
||
<ul class="md-select__list">
|
||
<li class="md-select__item">
|
||
<a class="md-select__link" href="/chapter_computational_complexity/summary/" hreflang="zh">
|
||
简体中文
|
||
</a>
|
||
</li>
|
||
<li class="md-select__item">
|
||
<a class="md-select__link" href="/zh-hant/chapter_computational_complexity/summary/" hreflang="zh-Hant">
|
||
繁體中文
|
||
</a>
|
||
</li>
|
||
<li class="md-select__item">
|
||
<a class="md-select__link" href="/en/chapter_computational_complexity/summary/" hreflang="en">
|
||
English
|
||
</a>
|
||
</li>
|
||
<li class="md-select__item">
|
||
<a class="md-select__link" href="/ja/chapter_computational_complexity/summary/" hreflang="ja">
|
||
日本語
|
||
</a>
|
||
</li>
|
||
<li class="md-select__item">
|
||
<a class="md-select__link" href="/ru/chapter_computational_complexity/summary/" hreflang="ru">
|
||
Русский
|
||
</a>
|
||
</li>
|
||
<li class="md-select__item">
|
||
<a class="md-select__link" href="/ko/chapter_computational_complexity/summary/" hreflang="ko">
|
||
한국어
|
||
</a>
|
||
</li>
|
||
</ul>
|
||
</div>
|
||
</div>
|
||
</div>
|
||
<label aria-label="Search" class="md-header__button md-icon" for="__search">
|
||
<svg class="lucide lucide-search" fill="none" stroke="currentColor" stroke-linecap="round" stroke-linejoin="round" stroke-width="2" viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="m21 21-4.34-4.34"></path><circle cx="11" cy="11" r="8"></circle></svg>
|
||
</label>
|
||
<div aria-label="Search" class="md-search" data-md-component="search" role="dialog">
|
||
<button class="md-search__button" type="button">
|
||
Search
|
||
</button>
|
||
</div>
|
||
<div class="md-header__source">
|
||
<a class="md-source" data-md-component="source" href="https://github.com/krahets/hello-algo" title="Go to repository">
|
||
<div class="md-source__icon md-icon">
|
||
<svg viewbox="0 0 512 512" xmlns="http://www.w3.org/2000/svg"><!--! Font Awesome Free 7.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2026 Fonticons, Inc.--><path d="M173.9 397.4c0 2-2.3 3.6-5.2 3.6-3.3.3-5.6-1.3-5.6-3.6 0-2 2.3-3.6 5.2-3.6 3-.3 5.6 1.3 5.6 3.6m-31.1-4.5c-.7 2 1.3 4.3 4.3 4.9 2.6 1 5.6 0 6.2-2s-1.3-4.3-4.3-5.2c-2.6-.7-5.5.3-6.2 2.3m44.2-1.7c-2.9.7-4.9 2.6-4.6 4.9.3 2 2.9 3.3 5.9 2.6 2.9-.7 4.9-2.6 4.6-4.6-.3-1.9-3-3.2-5.9-2.9M252.8 8C114.1 8 8 113.3 8 252c0 110.9 69.8 205.8 169.5 239.2 12.8 2.3 17.3-5.6 17.3-12.1 0-6.2-.3-40.4-.3-61.4 0 0-70 15-84.7-29.8 0 0-11.4-29.1-27.8-36.6 0 0-22.9-15.7 1.6-15.4 0 0 24.9 2 38.6 25.8 21.9 38.6 58.6 27.5 72.9 20.9 2.3-16 8.8-27.1 16-33.7-55.9-6.2-112.3-14.3-112.3-110.5 0-27.5 7.6-41.3 23.6-58.9-2.6-6.5-11.1-33.3 2.6-67.9 20.9-6.5 69 27 69 27 20-5.6 41.5-8.5 62.8-8.5s42.8 2.9 62.8 8.5c0 0 48.1-33.6 69-27 13.7 34.7 5.2 61.4 2.6 67.9 16 17.7 25.8 31.5 25.8 58.9 0 96.5-58.9 104.2-114.8 110.5 9.2 7.9 17 22.9 17 46.4 0 33.7-.3 75.4-.3 83.6 0 6.5 4.6 14.4 17.3 12.1C436.2 457.8 504 362.9 504 252 504 113.3 391.5 8 252.8 8M105.2 352.9c-1.3 1-1 3.3.7 5.2 1.6 1.6 3.9 2.3 5.2 1 1.3-1 1-3.3-.7-5.2-1.6-1.6-3.9-2.3-5.2-1m-10.8-8.1c-.7 1.3.3 2.9 2.3 3.9 1.6 1 3.6.7 4.3-.7.7-1.3-.3-2.9-2.3-3.9-2-.6-3.6-.3-4.3.7m32.4 35.6c-1.6 1.3-1 4.3 1.3 6.2 2.3 2.3 5.2 2.6 6.5 1 1.3-1.3.7-4.3-1.3-6.2-2.2-2.3-5.2-2.6-6.5-1m-11.4-14.7c-1.6 1-1.6 3.6 0 5.9s4.3 3.3 5.6 2.3c1.6-1.3 1.6-3.9 0-6.2-1.4-2.3-4-3.3-5.6-2" fill="currentColor"></path></svg>
|
||
</div>
|
||
<div class="md-source__repository">
|
||
krahets/hello-algo
|
||
</div>
|
||
</a>
|
||
</div>
|
||
</nav>
|
||
</header>
|
||
<div class="md-container" data-md-component="container">
|
||
<main class="md-main" data-md-component="main">
|
||
<div class="md-main__inner md-grid">
|
||
<div class="md-sidebar md-sidebar--primary" data-md-component="sidebar" data-md-type="navigation">
|
||
<div class="md-sidebar__scrollwrap">
|
||
<div class="md-sidebar__inner">
|
||
<nav aria-label="Navigation" class="md-nav md-nav--primary" data-md-level="0">
|
||
<label class="md-nav__title" for="__drawer">
|
||
<a aria-label="Hello Algo" class="md-nav__button md-logo" data-md-component="logo" href="../.." title="Hello Algo">
|
||
<img alt="Hello Algo" src="../../assets/images/logo.svg"/>
|
||
</a>
|
||
Hello Algo
|
||
</label>
|
||
<div class="md-nav__source">
|
||
<a class="md-source" data-md-component="source" href="https://github.com/krahets/hello-algo" title="Go to repository">
|
||
<div class="md-source__icon md-icon">
|
||
<svg viewbox="0 0 512 512" xmlns="http://www.w3.org/2000/svg"><!--! Font Awesome Free 7.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2026 Fonticons, Inc.--><path d="M173.9 397.4c0 2-2.3 3.6-5.2 3.6-3.3.3-5.6-1.3-5.6-3.6 0-2 2.3-3.6 5.2-3.6 3-.3 5.6 1.3 5.6 3.6m-31.1-4.5c-.7 2 1.3 4.3 4.3 4.9 2.6 1 5.6 0 6.2-2s-1.3-4.3-4.3-5.2c-2.6-.7-5.5.3-6.2 2.3m44.2-1.7c-2.9.7-4.9 2.6-4.6 4.9.3 2 2.9 3.3 5.9 2.6 2.9-.7 4.9-2.6 4.6-4.6-.3-1.9-3-3.2-5.9-2.9M252.8 8C114.1 8 8 113.3 8 252c0 110.9 69.8 205.8 169.5 239.2 12.8 2.3 17.3-5.6 17.3-12.1 0-6.2-.3-40.4-.3-61.4 0 0-70 15-84.7-29.8 0 0-11.4-29.1-27.8-36.6 0 0-22.9-15.7 1.6-15.4 0 0 24.9 2 38.6 25.8 21.9 38.6 58.6 27.5 72.9 20.9 2.3-16 8.8-27.1 16-33.7-55.9-6.2-112.3-14.3-112.3-110.5 0-27.5 7.6-41.3 23.6-58.9-2.6-6.5-11.1-33.3 2.6-67.9 20.9-6.5 69 27 69 27 20-5.6 41.5-8.5 62.8-8.5s42.8 2.9 62.8 8.5c0 0 48.1-33.6 69-27 13.7 34.7 5.2 61.4 2.6 67.9 16 17.7 25.8 31.5 25.8 58.9 0 96.5-58.9 104.2-114.8 110.5 9.2 7.9 17 22.9 17 46.4 0 33.7-.3 75.4-.3 83.6 0 6.5 4.6 14.4 17.3 12.1C436.2 457.8 504 362.9 504 252 504 113.3 391.5 8 252.8 8M105.2 352.9c-1.3 1-1 3.3.7 5.2 1.6 1.6 3.9 2.3 5.2 1 1.3-1 1-3.3-.7-5.2-1.6-1.6-3.9-2.3-5.2-1m-10.8-8.1c-.7 1.3.3 2.9 2.3 3.9 1.6 1 3.6.7 4.3-.7.7-1.3-.3-2.9-2.3-3.9-2-.6-3.6-.3-4.3.7m32.4 35.6c-1.6 1.3-1 4.3 1.3 6.2 2.3 2.3 5.2 2.6 6.5 1 1.3-1.3.7-4.3-1.3-6.2-2.2-2.3-5.2-2.6-6.5-1m-11.4-14.7c-1.6 1-1.6 3.6 0 5.9s4.3 3.3 5.6 2.3c1.6-1.3 1.6-3.9 0-6.2-1.4-2.3-4-3.3-5.6-2" fill="currentColor"></path></svg>
|
||
</div>
|
||
<div class="md-source__repository">
|
||
krahets/hello-algo
|
||
</div>
|
||
</a>
|
||
</div>
|
||
<ul class="md-nav__list" data-md-scrollfix="">
|
||
<li class="md-nav__item md-nav__item--nested">
|
||
<input class="md-nav__toggle md-toggle" id="__nav_1" type="checkbox"/>
|
||
<div class="md-nav__link md-nav__container">
|
||
<a class="md-nav__link" href="../../chapter_hello_algo/">
|
||
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="m13.13 22.19-1.63-3.83c1.57-.58 3.04-1.36 4.4-2.27zM5.64 12.5l-3.83-1.63 6.1-2.77C7 9.46 6.22 10.93 5.64 12.5M19.22 4c.28 0 .53 0 .74.05.17 1.39-.02 4.25-3.3 7.53-1.7 1.71-3.73 3.02-6.01 3.89l-2.15-2.1c.92-2.31 2.23-4.34 3.92-6.03C15.18 4.58 17.64 4 19.22 4m0-2c-1.98 0-4.98.69-8.22 3.93-2.19 2.19-3.5 4.6-4.35 6.71-.28.75-.09 1.57.46 2.13l2.13 2.12c.38.38.89.61 1.42.61.23 0 .47-.06.7-.15A19.1 19.1 0 0 0 18.07 13c5.66-5.66 3.54-10.61 3.54-10.61S20.7 2 19.22 2m-4.68 7.46c-.78-.78-.78-2.05 0-2.83s2.05-.78 2.83 0c.77.78.78 2.05 0 2.83s-2.05.78-2.83 0m-5.66 7.07-1.41-1.41zM6.24 22l3.64-3.64c-.34-.09-.67-.24-.97-.45L4.83 22zM2 22h1.41l4.77-4.76-1.42-1.41L2 20.59zm0-2.83 4.09-4.08c-.21-.3-.36-.62-.45-.97L2 17.76z"></path></svg>
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
Foreword
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</div>
|
||
<nav aria-expanded="false" aria-labelledby="__nav_1_label" class="md-nav" data-md-level="1">
|
||
<label class="md-nav__title" for="__nav_1">
|
||
<span class="md-nav__icon md-icon"></span>
|
||
|
||
|
||
Foreword
|
||
|
||
</label>
|
||
<ul class="md-nav__list" data-md-scrollfix="">
|
||
</ul>
|
||
</nav>
|
||
</li>
|
||
<li class="md-nav__item md-nav__item--nested">
|
||
<input class="md-nav__toggle md-toggle" id="__nav_2" type="checkbox"/>
|
||
<div class="md-nav__link md-nav__container">
|
||
<a class="md-nav__link" href="../../chapter_preface/">
|
||
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M21 4H3a2 2 0 0 0-2 2v13a2 2 0 0 0 2 2h18a2 2 0 0 0 2-2V6a2 2 0 0 0-2-2M3 19V6h8v13zm18 0h-8V6h8zm-7-9.5h6V11h-6zm0 2.5h6v1.5h-6zm0 2.5h6V16h-6z"></path></svg>
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
Chapter 0. Preface
|
||
|
||
|
||
</span>
|
||
</a>
|
||
<label class="md-nav__link" for="__nav_2" id="__nav_2_label" tabindex="0">
|
||
<span class="md-nav__icon md-icon"></span>
|
||
</label>
|
||
</div>
|
||
<nav aria-expanded="false" aria-labelledby="__nav_2_label" class="md-nav" data-md-level="1">
|
||
<label class="md-nav__title" for="__nav_2">
|
||
<span class="md-nav__icon md-icon"></span>
|
||
|
||
|
||
Chapter 0. Preface
|
||
|
||
</label>
|
||
<ul class="md-nav__list" data-md-scrollfix="">
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_preface/about_the_book/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
0.1 About this book
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_preface/suggestions/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
0.2 How to use this book
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_preface/summary/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
0.3 Summary
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
</ul>
|
||
</nav>
|
||
</li>
|
||
<li class="md-nav__item md-nav__item--nested">
|
||
<input class="md-nav__toggle md-toggle" id="__nav_3" type="checkbox"/>
|
||
<div class="md-nav__link md-nav__container">
|
||
<a class="md-nav__link" href="../../chapter_introduction/">
|
||
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M19 3H5c-1.1 0-2 .9-2 2v14c0 1.1.9 2 2 2h14c1.1 0 2-.9 2-2V5c0-1.1-.9-2-2-2m0 16H5V5h14zM6.2 7.7h5v1.5h-5zm6.8 8.1h5v1.5h-5zm0-2.6h5v1.5h-5zM8 18h1.5v-2h2v-1.5h-2v-2H8v2H6V16h2zm6.1-7.1 1.4-1.4 1.4 1.4 1.1-1-1.4-1.4L18 7.1 16.9 6l-1.4 1.4L14.1 6 13 7.1l1.4 1.4L13 9.9z"></path></svg>
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
Chapter 1. Getting to know algorithms
|
||
|
||
|
||
</span>
|
||
</a>
|
||
<label class="md-nav__link" for="__nav_3" id="__nav_3_label" tabindex="0">
|
||
<span class="md-nav__icon md-icon"></span>
|
||
</label>
|
||
</div>
|
||
<nav aria-expanded="false" aria-labelledby="__nav_3_label" class="md-nav" data-md-level="1">
|
||
<label class="md-nav__title" for="__nav_3">
|
||
<span class="md-nav__icon md-icon"></span>
|
||
|
||
|
||
Chapter 1. Getting to know algorithms
|
||
|
||
</label>
|
||
<ul class="md-nav__list" data-md-scrollfix="">
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_introduction/algorithms_are_everywhere/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
1.1 Algorithms are everywhere
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_introduction/what_is_dsa/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
1.2 What is an algorithm?
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_introduction/summary/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
1.3 Summary
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
</ul>
|
||
</nav>
|
||
</li>
|
||
<li class="md-nav__item md-nav__item--active md-nav__item--nested">
|
||
<input checked="" class="md-nav__toggle md-toggle" id="__nav_4" type="checkbox"/>
|
||
<div class="md-nav__link md-nav__container">
|
||
<a class="md-nav__link" href="../">
|
||
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M6 2h12v6l-4 4 4 4v6H6v-6l4-4-4-4zm10 14.5-4-4-4 4V20h8zm-4-5 4-4V4H8v3.5zM10 6h4v.75l-2 2-2-2z"></path></svg>
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
Chapter 2. Complexity analysis
|
||
|
||
|
||
</span>
|
||
</a>
|
||
<label class="md-nav__link" for="__nav_4" id="__nav_4_label" tabindex="0">
|
||
<span class="md-nav__icon md-icon"></span>
|
||
</label>
|
||
</div>
|
||
<nav aria-expanded="true" aria-labelledby="__nav_4_label" class="md-nav" data-md-level="1">
|
||
<label class="md-nav__title" for="__nav_4">
|
||
<span class="md-nav__icon md-icon"></span>
|
||
|
||
|
||
Chapter 2. Complexity analysis
|
||
|
||
</label>
|
||
<ul class="md-nav__list" data-md-scrollfix="">
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../performance_evaluation/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
2.1 Evaluating algorithm efficiency
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../iteration_and_recursion/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
2.2 Iteration and recursion
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../time_complexity/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
2.3 Time complexity
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../space_complexity/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
2.4 Space complexity
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item md-nav__item--active">
|
||
<label class="md-nav__link md-nav__link--active" for="__toc">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
2.5 Summary
|
||
|
||
|
||
</span>
|
||
<span class="md-nav__icon md-icon"></span>
|
||
</label>
|
||
<a class="md-nav__link md-nav__link--active" href="././">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
2.5 Summary
|
||
|
||
|
||
</span>
|
||
</a>
|
||
<nav aria-label="On this page" class="md-nav md-nav--secondary">
|
||
<label class="md-nav__title" for="__toc">
|
||
<span class="md-nav__icon md-icon"></span>
|
||
On this page
|
||
</label>
|
||
<ul class="md-nav__list" data-md-component="toc" data-md-scrollfix="">
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="#1-key-takeaways">
|
||
<span class="md-ellipsis">
|
||
<span class="md-typeset">
|
||
1. Key takeaways
|
||
</span>
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="#2-q-a">
|
||
<span class="md-ellipsis">
|
||
<span class="md-typeset">
|
||
2. Q & A
|
||
</span>
|
||
</span>
|
||
</a>
|
||
</li>
|
||
</ul>
|
||
</nav>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../exercises/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
2.6 Exercises
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
</ul>
|
||
</nav>
|
||
</li>
|
||
<li class="md-nav__item md-nav__item--nested">
|
||
<input class="md-nav__toggle md-toggle" id="__nav_5" type="checkbox"/>
|
||
<div class="md-nav__link md-nav__container">
|
||
<a class="md-nav__link" href="../../chapter_data_structure/">
|
||
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M11 13.5v8H3v-8zm-2 2H5v4h4zM12 2l5.5 9h-11zm0 3.86L10.08 9h3.84zM17.5 13c2.5 0 4.5 2 4.5 4.5S20 22 17.5 22 13 20 13 17.5s2-4.5 4.5-4.5m0 2a2.5 2.5 0 0 0-2.5 2.5 2.5 2.5 0 0 0 2.5 2.5 2.5 2.5 0 0 0 2.5-2.5 2.5 2.5 0 0 0-2.5-2.5"></path></svg>
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
Chapter 3. Data structures
|
||
|
||
|
||
</span>
|
||
</a>
|
||
<label class="md-nav__link" for="__nav_5" id="__nav_5_label" tabindex="0">
|
||
<span class="md-nav__icon md-icon"></span>
|
||
</label>
|
||
</div>
|
||
<nav aria-expanded="false" aria-labelledby="__nav_5_label" class="md-nav" data-md-level="1">
|
||
<label class="md-nav__title" for="__nav_5">
|
||
<span class="md-nav__icon md-icon"></span>
|
||
|
||
|
||
Chapter 3. Data structures
|
||
|
||
</label>
|
||
<ul class="md-nav__list" data-md-scrollfix="">
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_data_structure/classification_of_data_structure/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
3.1 Classifying data structures
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_data_structure/basic_data_types/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
3.2 Basic data types
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_data_structure/number_encoding/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
3.3 Number encoding *
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_data_structure/character_encoding/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
3.4 Character encoding *
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_data_structure/summary/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
3.5 Summary
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_data_structure/exercises/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
3.6 Exercises
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
</ul>
|
||
</nav>
|
||
</li>
|
||
<li class="md-nav__item md-nav__item--nested">
|
||
<input class="md-nav__toggle md-toggle" id="__nav_6" type="checkbox"/>
|
||
<div class="md-nav__link md-nav__container">
|
||
<a class="md-nav__link" href="../../chapter_array_and_linkedlist/">
|
||
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M3 5v14h17V5zm4 2v2H5V7zm-2 6v-2h2v2zm0 2h2v2H5zm13 2H9v-2h9zm0-4H9v-2h9zm0-4H9V7h9z"></path></svg>
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
Chapter 4. Arrays and linked lists
|
||
|
||
|
||
</span>
|
||
</a>
|
||
<label class="md-nav__link" for="__nav_6" id="__nav_6_label" tabindex="0">
|
||
<span class="md-nav__icon md-icon"></span>
|
||
</label>
|
||
</div>
|
||
<nav aria-expanded="false" aria-labelledby="__nav_6_label" class="md-nav" data-md-level="1">
|
||
<label class="md-nav__title" for="__nav_6">
|
||
<span class="md-nav__icon md-icon"></span>
|
||
|
||
|
||
Chapter 4. Arrays and linked lists
|
||
|
||
</label>
|
||
<ul class="md-nav__list" data-md-scrollfix="">
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_array_and_linkedlist/array/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
4.1 Arrays
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_array_and_linkedlist/linked_list/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
4.2 Linked lists
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_array_and_linkedlist/list/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
4.3 Lists
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_array_and_linkedlist/ram_and_cache/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
4.4 Memory and cache *
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_array_and_linkedlist/summary/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
4.5 Summary
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_array_and_linkedlist/exercises/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
4.6 Exercises
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
</ul>
|
||
</nav>
|
||
</li>
|
||
<li class="md-nav__item md-nav__item--nested">
|
||
<input class="md-nav__toggle md-toggle" id="__nav_7" type="checkbox"/>
|
||
<div class="md-nav__link md-nav__container">
|
||
<a class="md-nav__link" href="../../chapter_stack_and_queue/">
|
||
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M17.36 20.2v-5.38h1.79V22H3v-7.18h1.8v5.38zM6.77 14.32l.37-1.76 8.79 1.85-.37 1.76zm1.16-4.21.76-1.61 8.14 3.78-.76 1.62zm2.26-3.99 1.15-1.38 6.9 5.76-1.15 1.37zm4.45-4.25L20 9.08l-1.44 1.07-5.36-7.21zM6.59 18.41v-1.8h8.98v1.8z"></path></svg>
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
Chapter 5. Stacks and queues
|
||
|
||
|
||
</span>
|
||
</a>
|
||
<label class="md-nav__link" for="__nav_7" id="__nav_7_label" tabindex="0">
|
||
<span class="md-nav__icon md-icon"></span>
|
||
</label>
|
||
</div>
|
||
<nav aria-expanded="false" aria-labelledby="__nav_7_label" class="md-nav" data-md-level="1">
|
||
<label class="md-nav__title" for="__nav_7">
|
||
<span class="md-nav__icon md-icon"></span>
|
||
|
||
|
||
Chapter 5. Stacks and queues
|
||
|
||
</label>
|
||
<ul class="md-nav__list" data-md-scrollfix="">
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_stack_and_queue/stack/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
5.1 Stacks
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_stack_and_queue/queue/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
5.2 Queues
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_stack_and_queue/deque/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
5.3 Deques
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_stack_and_queue/summary/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
5.4 Summary
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_stack_and_queue/exercises/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
5.5 Exercises
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
</ul>
|
||
</nav>
|
||
</li>
|
||
<li class="md-nav__item md-nav__item--nested">
|
||
<input class="md-nav__toggle md-toggle" id="__nav_8" type="checkbox"/>
|
||
<div class="md-nav__link md-nav__container">
|
||
<a class="md-nav__link" href="../../chapter_hashing/">
|
||
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M19.3 17.89c1.32-2.1.7-4.89-1.41-6.21a4.52 4.52 0 0 0-6.21 1.41C10.36 15.2 11 18 13.09 19.3c1.47.92 3.33.92 4.8 0L21 22.39 22.39 21zm-2-.62c-.98.98-2.56.97-3.54 0-.97-.98-.97-2.56.01-3.54.97-.97 2.55-.97 3.53 0 .96.99.95 2.57-.03 3.54zM19 4H5a2 2 0 0 0-2 2v12a2 2 0 0 0 2 2h5.81a6.3 6.3 0 0 1-1.31-2H5v-4h4.18c.16-.71.43-1.39.82-2H5V8h6v2.81a6.3 6.3 0 0 1 2-1.31V8h6v2a6.499 6.499 0 0 1 2 2V6a2 2 0 0 0-2-2"></path></svg>
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
Chapter 6. Hash tables
|
||
|
||
|
||
</span>
|
||
</a>
|
||
<label class="md-nav__link" for="__nav_8" id="__nav_8_label" tabindex="0">
|
||
<span class="md-nav__icon md-icon"></span>
|
||
</label>
|
||
</div>
|
||
<nav aria-expanded="false" aria-labelledby="__nav_8_label" class="md-nav" data-md-level="1">
|
||
<label class="md-nav__title" for="__nav_8">
|
||
<span class="md-nav__icon md-icon"></span>
|
||
|
||
|
||
Chapter 6. Hash tables
|
||
|
||
</label>
|
||
<ul class="md-nav__list" data-md-scrollfix="">
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_hashing/hash_map/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
6.1 Hash tables
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_hashing/hash_collision/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
6.2 Hash collisions
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_hashing/hash_algorithm/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
6.3 Hash algorithms
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_hashing/summary/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
6.4 Summary
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_hashing/exercises/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
6.5 Exercises
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
</ul>
|
||
</nav>
|
||
</li>
|
||
<li class="md-nav__item md-nav__item--nested">
|
||
<input class="md-nav__toggle md-toggle" id="__nav_9" type="checkbox"/>
|
||
<div class="md-nav__link md-nav__container">
|
||
<a class="md-nav__link" href="../../chapter_tree/">
|
||
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M19.5 17c-.14 0-.26 0-.39.04L17.5 13.8c.45-.45.75-1.09.75-1.8a2.5 2.5 0 0 0-2.5-2.5c-.14 0-.25 0-.4.04L13.74 6.3c.47-.46.76-1.09.76-1.8a2.5 2.5 0 0 0-5 0c0 .7.29 1.34.76 1.79L8.65 9.54c-.15-.04-.26-.04-.4-.04a2.5 2.5 0 0 0-2.5 2.5c0 .71.29 1.34.75 1.79l-1.61 3.25C4.76 17 4.64 17 4.5 17a2.5 2.5 0 0 0 0 5A2.5 2.5 0 0 0 7 19.5c0-.7-.29-1.34-.76-1.79l1.62-3.25c.14.04.26.04.39.04s.25 0 .38-.04l1.63 3.25c-.47.45-.76 1.09-.76 1.79a2.5 2.5 0 0 0 5 0A2.5 2.5 0 0 0 12 17c-.13 0-.26 0-.39.04L10 13.8c.45-.45.75-1.09.75-1.8 0-.7-.29-1.33-.75-1.79l1.61-3.25c.13.04.26.04.39.04s.26 0 .39-.04L14 10.21a2.5 2.5 0 0 0 1.75 4.29c.13 0 .25 0 .38-.04l1.63 3.25c-.47.45-.76 1.09-.76 1.79a2.5 2.5 0 0 0 5 0 2.5 2.5 0 0 0-2.5-2.5m-15 3.5c-.55 0-1-.45-1-1s.45-1 1-1 1 .45 1 1-.45 1-1 1m8.5-1c0 .55-.45 1-1 1s-1-.45-1-1 .45-1 1-1 1 .45 1 1M7.25 12c0-.55.45-1 1-1s1 .45 1 1-.45 1-1 1-1-.45-1-1M11 4.5c0-.55.45-1 1-1s1 .45 1 1-.45 1-1 1-1-.45-1-1m3.75 7.5c0-.55.45-1 1-1s1 .45 1 1-.45 1-1 1-1-.45-1-1m4.75 8.5c-.55 0-1-.45-1-1s.45-1 1-1 1 .45 1 1-.45 1-1 1"></path></svg>
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
Chapter 7. Trees
|
||
|
||
|
||
</span>
|
||
</a>
|
||
<label class="md-nav__link" for="__nav_9" id="__nav_9_label" tabindex="0">
|
||
<span class="md-nav__icon md-icon"></span>
|
||
</label>
|
||
</div>
|
||
<nav aria-expanded="false" aria-labelledby="__nav_9_label" class="md-nav" data-md-level="1">
|
||
<label class="md-nav__title" for="__nav_9">
|
||
<span class="md-nav__icon md-icon"></span>
|
||
|
||
|
||
Chapter 7. Trees
|
||
|
||
</label>
|
||
<ul class="md-nav__list" data-md-scrollfix="">
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_tree/binary_tree/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
7.1 Binary trees
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_tree/binary_tree_traversal/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
7.2 Traversing a binary tree
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_tree/array_representation_of_tree/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
7.3 Array representation of a binary tree
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_tree/binary_search_tree/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
7.4 Binary search trees
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_tree/avl_tree/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
7.5 AVL trees *
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_tree/summary/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
7.6 Summary
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_tree/exercises/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
7.7 Exercises
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
</ul>
|
||
</nav>
|
||
</li>
|
||
<li class="md-nav__item md-nav__item--nested">
|
||
<input class="md-nav__toggle md-toggle" id="__nav_10" type="checkbox"/>
|
||
<div class="md-nav__link md-nav__container">
|
||
<a class="md-nav__link" href="../../chapter_heap/">
|
||
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M12 1a2.5 2.5 0 0 0-2.5 2.5A2.5 2.5 0 0 0 11 5.79V7H7a2 2 0 0 0-2 2v.71A2.5 2.5 0 0 0 3.5 12 2.5 2.5 0 0 0 5 14.29V15H4a2 2 0 0 0-2 2v1.21A2.5 2.5 0 0 0 .5 20.5 2.5 2.5 0 0 0 3 23a2.5 2.5 0 0 0 2.5-2.5A2.5 2.5 0 0 0 4 18.21V17h4v1.21a2.5 2.5 0 0 0-1.5 2.29A2.5 2.5 0 0 0 9 23a2.5 2.5 0 0 0 2.5-2.5 2.5 2.5 0 0 0-1.5-2.29V17a2 2 0 0 0-2-2H7v-.71A2.5 2.5 0 0 0 8.5 12 2.5 2.5 0 0 0 7 9.71V9h10v.71A2.5 2.5 0 0 0 15.5 12a2.5 2.5 0 0 0 1.5 2.29V15h-1a2 2 0 0 0-2 2v1.21a2.5 2.5 0 0 0-1.5 2.29A2.5 2.5 0 0 0 15 23a2.5 2.5 0 0 0 2.5-2.5 2.5 2.5 0 0 0-1.5-2.29V17h4v1.21a2.5 2.5 0 0 0-1.5 2.29A2.5 2.5 0 0 0 21 23a2.5 2.5 0 0 0 2.5-2.5 2.5 2.5 0 0 0-1.5-2.29V17a2 2 0 0 0-2-2h-1v-.71A2.5 2.5 0 0 0 20.5 12 2.5 2.5 0 0 0 19 9.71V9a2 2 0 0 0-2-2h-4V5.79a2.5 2.5 0 0 0 1.5-2.29A2.5 2.5 0 0 0 12 1m0 1.5a1 1 0 0 1 1 1 1 1 0 0 1-1 1 1 1 0 0 1-1-1 1 1 0 0 1 1-1M6 11a1 1 0 0 1 1 1 1 1 0 0 1-1 1 1 1 0 0 1-1-1 1 1 0 0 1 1-1m12 0a1 1 0 0 1 1 1 1 1 0 0 1-1 1 1 1 0 0 1-1-1 1 1 0 0 1 1-1M3 19.5a1 1 0 0 1 1 1 1 1 0 0 1-1 1 1 1 0 0 1-1-1 1 1 0 0 1 1-1m6 0a1 1 0 0 1 1 1 1 1 0 0 1-1 1 1 1 0 0 1-1-1 1 1 0 0 1 1-1m6 0a1 1 0 0 1 1 1 1 1 0 0 1-1 1 1 1 0 0 1-1-1 1 1 0 0 1 1-1m6 0a1 1 0 0 1 1 1 1 1 0 0 1-1 1 1 1 0 0 1-1-1 1 1 0 0 1 1-1"></path></svg>
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
Chapter 8. Heaps
|
||
|
||
|
||
</span>
|
||
</a>
|
||
<label class="md-nav__link" for="__nav_10" id="__nav_10_label" tabindex="0">
|
||
<span class="md-nav__icon md-icon"></span>
|
||
</label>
|
||
</div>
|
||
<nav aria-expanded="false" aria-labelledby="__nav_10_label" class="md-nav" data-md-level="1">
|
||
<label class="md-nav__title" for="__nav_10">
|
||
<span class="md-nav__icon md-icon"></span>
|
||
|
||
|
||
Chapter 8. Heaps
|
||
|
||
</label>
|
||
<ul class="md-nav__list" data-md-scrollfix="">
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_heap/heap/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
8.1 Heaps
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_heap/build_heap/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
8.2 Building a heap
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_heap/top_k/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
8.3 The top-k problem
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_heap/summary/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
8.4 Summary
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_heap/exercises/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
8.5 Exercises
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
</ul>
|
||
</nav>
|
||
</li>
|
||
<li class="md-nav__item md-nav__item--nested">
|
||
<input class="md-nav__toggle md-toggle" id="__nav_11" type="checkbox"/>
|
||
<div class="md-nav__link md-nav__container">
|
||
<a class="md-nav__link" href="../../chapter_graph/">
|
||
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="m12 5.37-.44-.06L6 14.9c.24.21.4.48.47.78h11.06c.07-.3.23-.57.47-.78l-5.56-9.59zM6.6 16.53l4.28 2.53c.29-.27.69-.43 1.12-.43s.83.16 1.12.43l4.28-2.53zM12 22a1.68 1.68 0 0 1-1.68-1.68l.09-.56-4.3-2.55c-.31.36-.76.58-1.27.58a1.68 1.68 0 0 1-1.68-1.68c0-.79.53-1.45 1.26-1.64V9.36c-.83-.11-1.47-.82-1.47-1.68A1.68 1.68 0 0 1 4.63 6c.55 0 1.03.26 1.34.66l4.41-2.53-.06-.45c0-.93.75-1.68 1.68-1.68s1.68.75 1.68 1.68l-.06.45 4.41 2.53c.31-.4.79-.66 1.34-.66a1.68 1.68 0 0 1 1.68 1.68c0 .86-.64 1.57-1.47 1.68v5.11c.73.19 1.26.85 1.26 1.64a1.68 1.68 0 0 1-1.68 1.68c-.51 0-.96-.22-1.27-.58l-4.3 2.55.09.56A1.68 1.68 0 0 1 12 22M10.8 4.86 6.3 7.44l.02.24c0 .71-.44 1.32-1.06 1.57l.03 5.25zm2.4 0 5.51 9.64.03-5.25c-.62-.25-1.06-.86-1.06-1.57l.02-.24z"></path></svg>
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
Chapter 9. Graphs
|
||
|
||
|
||
</span>
|
||
</a>
|
||
<label class="md-nav__link" for="__nav_11" id="__nav_11_label" tabindex="0">
|
||
<span class="md-nav__icon md-icon"></span>
|
||
</label>
|
||
</div>
|
||
<nav aria-expanded="false" aria-labelledby="__nav_11_label" class="md-nav" data-md-level="1">
|
||
<label class="md-nav__title" for="__nav_11">
|
||
<span class="md-nav__icon md-icon"></span>
|
||
|
||
|
||
Chapter 9. Graphs
|
||
|
||
</label>
|
||
<ul class="md-nav__list" data-md-scrollfix="">
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_graph/graph/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
9.1 Graphs
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_graph/graph_operations/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
9.2 Basic graph operations
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_graph/graph_traversal/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
9.3 Graph traversal
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_graph/summary/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
9.4 Summary
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_graph/exercises/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
9.5 Exercises
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
</ul>
|
||
</nav>
|
||
</li>
|
||
<li class="md-nav__item md-nav__item--nested">
|
||
<input class="md-nav__toggle md-toggle" id="__nav_12" type="checkbox"/>
|
||
<div class="md-nav__link md-nav__container">
|
||
<a class="md-nav__link" href="../../chapter_searching/">
|
||
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="m19.31 18.9 3.08 3.1L21 23.39l-3.12-3.07c-.69.43-1.51.68-2.38.68-2.5 0-4.5-2-4.5-4.5s2-4.5 4.5-4.5 4.5 2 4.5 4.5c0 .88-.25 1.71-.69 2.4m-3.81.1a2.5 2.5 0 0 0 0-5 2.5 2.5 0 0 0 0 5M21 4v2H3V4zM3 16v-2h6v2zm0-5V9h18v2h-2.03c-1.01-.63-2.2-1-3.47-1s-2.46.37-3.47 1z"></path></svg>
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
Chapter 10. Searching
|
||
|
||
|
||
</span>
|
||
</a>
|
||
<label class="md-nav__link" for="__nav_12" id="__nav_12_label" tabindex="0">
|
||
<span class="md-nav__icon md-icon"></span>
|
||
</label>
|
||
</div>
|
||
<nav aria-expanded="false" aria-labelledby="__nav_12_label" class="md-nav" data-md-level="1">
|
||
<label class="md-nav__title" for="__nav_12">
|
||
<span class="md-nav__icon md-icon"></span>
|
||
|
||
|
||
Chapter 10. Searching
|
||
|
||
</label>
|
||
<ul class="md-nav__list" data-md-scrollfix="">
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_searching/binary_search/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
10.1 Binary search
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_searching/binary_search_insertion/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
10.2 Finding an insertion point with binary search
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_searching/binary_search_edge/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
10.3 Finding boundaries with binary search
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_searching/replace_linear_by_hashing/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
10.4 Optimizing with hashing
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_searching/searching_algorithm_revisited/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
10.5 Search algorithms revisited
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_searching/summary/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
10.6 Summary
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_searching/exercises/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
10.7 Exercises
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
</ul>
|
||
</nav>
|
||
</li>
|
||
<li class="md-nav__item md-nav__item--nested">
|
||
<input class="md-nav__toggle md-toggle" id="__nav_13" type="checkbox"/>
|
||
<div class="md-nav__link md-nav__container">
|
||
<a class="md-nav__link" href="../../chapter_sorting/">
|
||
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M19 17h3l-4 4-4-4h3V3h2M2 17h10v2H2M6 5v2H2V5m0 6h7v2H2z"></path></svg>
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
Chapter 11. Sorting
|
||
|
||
|
||
</span>
|
||
</a>
|
||
<label class="md-nav__link" for="__nav_13" id="__nav_13_label" tabindex="0">
|
||
<span class="md-nav__icon md-icon"></span>
|
||
</label>
|
||
</div>
|
||
<nav aria-expanded="false" aria-labelledby="__nav_13_label" class="md-nav" data-md-level="1">
|
||
<label class="md-nav__title" for="__nav_13">
|
||
<span class="md-nav__icon md-icon"></span>
|
||
|
||
|
||
Chapter 11. Sorting
|
||
|
||
</label>
|
||
<ul class="md-nav__list" data-md-scrollfix="">
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_sorting/sorting_algorithm/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
11.1 Sorting algorithms
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_sorting/selection_sort/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
11.2 Selection sort
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_sorting/bubble_sort/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
11.3 Bubble sort
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_sorting/insertion_sort/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
11.4 Insertion sort
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_sorting/quick_sort/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
11.5 Quick sort
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_sorting/merge_sort/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
11.6 Merge sort
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_sorting/heap_sort/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
11.7 Heap sort
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_sorting/bucket_sort/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
11.8 Bucket sort
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_sorting/counting_sort/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
11.9 Counting sort
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_sorting/radix_sort/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
11.10 Radix sort
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_sorting/summary/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
11.11 Summary
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_sorting/exercises/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
11.12 Exercises
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
</ul>
|
||
</nav>
|
||
</li>
|
||
<li class="md-nav__item md-nav__item--nested">
|
||
<input class="md-nav__toggle md-toggle" id="__nav_14" type="checkbox"/>
|
||
<div class="md-nav__link md-nav__container">
|
||
<a class="md-nav__link" href="../../chapter_divide_and_conquer/">
|
||
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M17 7v2h5V7zM2 9v6h5V9zm10 0v2H9v2h3v2l3-3zm5 2v2h5v-2zm0 4v2h5v-2z"></path></svg>
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
Chapter 12. Divide and conquer
|
||
|
||
|
||
</span>
|
||
</a>
|
||
<label class="md-nav__link" for="__nav_14" id="__nav_14_label" tabindex="0">
|
||
<span class="md-nav__icon md-icon"></span>
|
||
</label>
|
||
</div>
|
||
<nav aria-expanded="false" aria-labelledby="__nav_14_label" class="md-nav" data-md-level="1">
|
||
<label class="md-nav__title" for="__nav_14">
|
||
<span class="md-nav__icon md-icon"></span>
|
||
|
||
|
||
Chapter 12. Divide and conquer
|
||
|
||
</label>
|
||
<ul class="md-nav__list" data-md-scrollfix="">
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_divide_and_conquer/divide_and_conquer/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
12.1 Divide and conquer
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_divide_and_conquer/binary_search_recur/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
12.2 Divide-and-conquer search
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_divide_and_conquer/build_binary_tree_problem/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
12.3 Building a binary tree
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_divide_and_conquer/hanota_problem/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
12.4 Tower of Hanoi
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_divide_and_conquer/summary/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
12.5 Summary
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_divide_and_conquer/exercises/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
12.6 Exercises
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
</ul>
|
||
</nav>
|
||
</li>
|
||
<li class="md-nav__item md-nav__item--nested">
|
||
<input class="md-nav__toggle md-toggle" id="__nav_15" type="checkbox"/>
|
||
<div class="md-nav__link md-nav__container">
|
||
<a class="md-nav__link" href="../../chapter_backtracking/">
|
||
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M18 15a3 3 0 0 1 3 3 3 3 0 0 1-3 3 2.99 2.99 0 0 1-2.83-2H14v-2h1.17c.41-1.17 1.52-2 2.83-2m0 2a1 1 0 0 0-1 1 1 1 0 0 0 1 1 1 1 0 0 0 1-1 1 1 0 0 0-1-1m0-9a1.43 1.43 0 0 0 1.43-1.43 1.43 1.43 0 1 0-2.86 0A1.43 1.43 0 0 0 18 8m0-5.43a4 4 0 0 1 4 4C22 9.56 18 14 18 14s-4-4.44-4-7.43a4 4 0 0 1 4-4M8.83 17H10v2H8.83A2.99 2.99 0 0 1 6 21a3 3 0 0 1-3-3c0-1.31.83-2.42 2-2.83V14h2v1.17c.85.3 1.53.98 1.83 1.83M6 17a1 1 0 0 0-1 1 1 1 0 0 0 1 1 1 1 0 0 0 1-1 1 1 0 0 0-1-1M6 3a3 3 0 0 1 3 3c0 1.31-.83 2.42-2 2.83V10H5V8.83A2.99 2.99 0 0 1 3 6a3 3 0 0 1 3-3m0 2a1 1 0 0 0-1 1 1 1 0 0 0 1 1 1 1 0 0 0 1-1 1 1 0 0 0-1-1m5 14v-2h2v2zm-4-6H5v-2h2z"></path></svg>
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
Chapter 13. Backtracking
|
||
|
||
|
||
</span>
|
||
</a>
|
||
<label class="md-nav__link" for="__nav_15" id="__nav_15_label" tabindex="0">
|
||
<span class="md-nav__icon md-icon"></span>
|
||
</label>
|
||
</div>
|
||
<nav aria-expanded="false" aria-labelledby="__nav_15_label" class="md-nav" data-md-level="1">
|
||
<label class="md-nav__title" for="__nav_15">
|
||
<span class="md-nav__icon md-icon"></span>
|
||
|
||
|
||
Chapter 13. Backtracking
|
||
|
||
</label>
|
||
<ul class="md-nav__list" data-md-scrollfix="">
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_backtracking/backtracking_algorithm/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
13.1 Backtracking algorithms
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_backtracking/permutations_problem/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
13.2 Permutations problem
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_backtracking/subset_sum_problem/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
13.3 Subset sum problem
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_backtracking/n_queens_problem/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
13.4 N-queens problem
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_backtracking/summary/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
13.5 Summary
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_backtracking/exercises/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
13.6 Exercises
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
</ul>
|
||
</nav>
|
||
</li>
|
||
<li class="md-nav__item md-nav__item--nested">
|
||
<input class="md-nav__toggle md-toggle" id="__nav_16" type="checkbox"/>
|
||
<div class="md-nav__link md-nav__container">
|
||
<a class="md-nav__link" href="../../chapter_dynamic_programming/">
|
||
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M22 15h-2v3c0 1.11-.89 2-2 2h-3v2l-3-3 3-3v2h3v-3h-2l3-3zm0-11v4c0 1.1-.9 2-2 2H10v10c0 1.1-.9 2-2 2H4c-1.1 0-2-.9-2-2V4c0-1.1.9-2 2-2h16c1.1 0 2 .9 2 2M4 8h4V4H4zm0 2v4h4v-4zm4 10v-4H4v4zm6-12V4h-4v4zm6-4h-4v4h4z"></path></svg>
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
Chapter 14. Dynamic programming
|
||
|
||
|
||
</span>
|
||
</a>
|
||
<label class="md-nav__link" for="__nav_16" id="__nav_16_label" tabindex="0">
|
||
<span class="md-nav__icon md-icon"></span>
|
||
</label>
|
||
</div>
|
||
<nav aria-expanded="false" aria-labelledby="__nav_16_label" class="md-nav" data-md-level="1">
|
||
<label class="md-nav__title" for="__nav_16">
|
||
<span class="md-nav__icon md-icon"></span>
|
||
|
||
|
||
Chapter 14. Dynamic programming
|
||
|
||
</label>
|
||
<ul class="md-nav__list" data-md-scrollfix="">
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_dynamic_programming/intro_to_dynamic_programming/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
14.1 Introduction to dynamic programming
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_dynamic_programming/dp_problem_features/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
14.2 Properties of dynamic programming problems
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_dynamic_programming/dp_solution_pipeline/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
14.3 Solving dynamic programming problems
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_dynamic_programming/knapsack_problem/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
14.4 0-1 knapsack problem
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_dynamic_programming/unbounded_knapsack_problem/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
14.5 Unbounded knapsack problem
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_dynamic_programming/edit_distance_problem/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
14.6 Edit distance problem
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_dynamic_programming/summary/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
14.7 Summary
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_dynamic_programming/exercises/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
14.8 Exercises
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
</ul>
|
||
</nav>
|
||
</li>
|
||
<li class="md-nav__item md-nav__item--nested">
|
||
<input class="md-nav__toggle md-toggle" id="__nav_17" type="checkbox"/>
|
||
<div class="md-nav__link md-nav__container">
|
||
<a class="md-nav__link" href="../../chapter_greedy/">
|
||
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M13 3c3.88 0 7 3.14 7 7 0 2.8-1.63 5.19-4 6.31V21H9v-3H8c-1.11 0-2-.89-2-2v-3H4.5c-.42 0-.66-.5-.42-.81L6 9.66A7.003 7.003 0 0 1 13 3m0-2C8.41 1 4.61 4.42 4.06 8.9L2.5 11h-.03l-.02.03c-.55.76-.62 1.76-.19 2.59.36.69 1 1.17 1.74 1.32V16c0 1.85 1.28 3.42 3 3.87V23h11v-5.5c2.5-1.67 4-4.44 4-7.5 0-4.97-4.04-9-9-9m4 7.83c0 1.54-1.36 2.77-3.42 4.64L13 14l-.58-.53C10.36 11.6 9 10.37 9 8.83c0-1.2.96-2.19 2.16-2.2h.04c.69 0 1.35.31 1.8.83.45-.52 1.11-.83 1.8-.83 1.2-.01 2.2.96 2.2 2.16z"></path></svg>
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
Chapter 15. Greedy algorithms
|
||
|
||
|
||
</span>
|
||
</a>
|
||
<label class="md-nav__link" for="__nav_17" id="__nav_17_label" tabindex="0">
|
||
<span class="md-nav__icon md-icon"></span>
|
||
</label>
|
||
</div>
|
||
<nav aria-expanded="false" aria-labelledby="__nav_17_label" class="md-nav" data-md-level="1">
|
||
<label class="md-nav__title" for="__nav_17">
|
||
<span class="md-nav__icon md-icon"></span>
|
||
|
||
|
||
Chapter 15. Greedy algorithms
|
||
|
||
</label>
|
||
<ul class="md-nav__list" data-md-scrollfix="">
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_greedy/greedy_algorithm/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
15.1 Greedy algorithms
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_greedy/fractional_knapsack_problem/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
15.2 Fractional knapsack problem
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_greedy/max_capacity_problem/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
15.3 Maximum capacity problem
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_greedy/max_product_cutting_problem/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
15.4 Maximum product cutting problem
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_greedy/summary/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
15.5 Summary
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_greedy/exercises/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
15.6 Exercises
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
</ul>
|
||
</nav>
|
||
</li>
|
||
<li class="md-nav__item md-nav__item--nested">
|
||
<input class="md-nav__toggle md-toggle" id="__nav_18" type="checkbox"/>
|
||
<div class="md-nav__link md-nav__container">
|
||
<a class="md-nav__link" href="../../chapter_appendix/">
|
||
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M11 18h2v-2h-2zm1-16A10 10 0 0 0 2 12a10 10 0 0 0 10 10 10 10 0 0 0 10-10A10 10 0 0 0 12 2m0 18c-4.41 0-8-3.59-8-8s3.59-8 8-8 8 3.59 8 8-3.59 8-8 8m0-14a4 4 0 0 0-4 4h2a2 2 0 0 1 2-2 2 2 0 0 1 2 2c0 2-3 1.75-3 5h2c0-2.25 3-2.5 3-5a4 4 0 0 0-4-4"></path></svg>
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
Chapter 16. Appendix
|
||
|
||
|
||
</span>
|
||
</a>
|
||
<label class="md-nav__link" for="__nav_18" id="__nav_18_label" tabindex="0">
|
||
<span class="md-nav__icon md-icon"></span>
|
||
</label>
|
||
</div>
|
||
<nav aria-expanded="false" aria-labelledby="__nav_18_label" class="md-nav" data-md-level="1">
|
||
<label class="md-nav__title" for="__nav_18">
|
||
<span class="md-nav__icon md-icon"></span>
|
||
|
||
|
||
Chapter 16. Appendix
|
||
|
||
</label>
|
||
<ul class="md-nav__list" data-md-scrollfix="">
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_appendix/installation/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
16.1 Setting up a programming environment
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_appendix/contribution/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
16.2 Contribute to the book
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="../../chapter_appendix/terminology/">
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
16.3 Glossary
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</li>
|
||
</ul>
|
||
</nav>
|
||
</li>
|
||
<li class="md-nav__item md-nav__item--nested">
|
||
<input class="md-nav__toggle md-toggle" id="__nav_19" type="checkbox"/>
|
||
<div class="md-nav__link md-nav__container">
|
||
<a class="md-nav__link" href="../../chapter_reference/">
|
||
<svg viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M9 3v15h3V3zm3 2 4 13 3-1-4-13zM5 5v13h3V5zM3 19v2h18v-2z"></path></svg>
|
||
<span class="md-ellipsis">
|
||
|
||
|
||
References
|
||
|
||
|
||
</span>
|
||
</a>
|
||
</div>
|
||
<nav aria-expanded="false" aria-labelledby="__nav_19_label" class="md-nav" data-md-level="1">
|
||
<label class="md-nav__title" for="__nav_19">
|
||
<span class="md-nav__icon md-icon"></span>
|
||
|
||
|
||
References
|
||
|
||
</label>
|
||
<ul class="md-nav__list" data-md-scrollfix="">
|
||
</ul>
|
||
</nav>
|
||
</li>
|
||
</ul>
|
||
</nav>
|
||
</div>
|
||
</div>
|
||
</div>
|
||
<div class="md-sidebar md-sidebar--secondary" data-md-component="sidebar" data-md-type="toc">
|
||
<div class="md-sidebar__scrollwrap">
|
||
<input class="md-nav__toggle md-toggle" id="__toc" type="checkbox"/>
|
||
<div class="md-sidebar-button__wrapper">
|
||
<label class="md-sidebar-button" for="__toc"></label>
|
||
</div>
|
||
<div class="md-sidebar__inner">
|
||
<nav aria-label="On this page" class="md-nav md-nav--secondary">
|
||
<label class="md-nav__title" for="__toc">
|
||
<span class="md-nav__icon md-icon"></span>
|
||
On this page
|
||
</label>
|
||
<ul class="md-nav__list" data-md-component="toc" data-md-scrollfix="">
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="#1-key-takeaways">
|
||
<span class="md-ellipsis">
|
||
<span class="md-typeset">
|
||
1. Key takeaways
|
||
</span>
|
||
</span>
|
||
</a>
|
||
</li>
|
||
<li class="md-nav__item">
|
||
<a class="md-nav__link" href="#2-q-a">
|
||
<span class="md-ellipsis">
|
||
<span class="md-typeset">
|
||
2. Q & A
|
||
</span>
|
||
</span>
|
||
</a>
|
||
</li>
|
||
</ul>
|
||
</nav>
|
||
</div>
|
||
</div>
|
||
</div>
|
||
<div class="md-content" data-md-component="content">
|
||
<article class="md-content__inner md-typeset">
|
||
<!-- Tags -->
|
||
<!-- Actions -->
|
||
<!-- Actions -->
|
||
<!-- Edit button -->
|
||
<a class="md-content__button md-icon" href="https://github.com/krahets/hello-algo/tree/main/en/docs/chapter_computational_complexity/summary.md" title="Edit this page">
|
||
<svg viewbox="0 0 512 512" xmlns="http://www.w3.org/2000/svg"><!--! Font Awesome Free 7.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2026 Fonticons, Inc.--><path d="M441 58.9 453.1 71c9.4 9.4 9.4 24.6 0 33.9L424 134.1 377.9 88 407 58.9c9.4-9.4 24.6-9.4 33.9 0zM209.8 256.2 344 121.9l46.1 46.1-134.3 134.2c-2.9 2.9-6.5 5-10.4 6.1L186.9 325l16.7-58.5c1.1-3.9 3.2-7.5 6.1-10.4zM373.1 25 175.8 222.2c-8.7 8.7-15 19.4-18.3 31.1l-28.6 100c-2.4 8.4-.1 17.4 6.1 23.6s15.2 8.5 23.6 6.1l100-28.6c11.8-3.4 22.5-9.7 31.1-18.3L487 138.9c28.1-28.1 28.1-73.7 0-101.8L474.9 25c-28.1-28.1-73.7-28.1-101.8 0M88 64c-48.6 0-88 39.4-88 88v272c0 48.6 39.4 88 88 88h272c48.6 0 88-39.4 88-88V312c0-13.3-10.7-24-24-24s-24 10.7-24 24v112c0 22.1-17.9 40-40 40H88c-22.1 0-40-17.9-40-40V152c0-22.1 17.9-40 40-40h112c13.3 0 24-10.7 24-24s-10.7-24-24-24z" fill="currentColor"></path></svg>
|
||
</a>
|
||
<!-- View button -->
|
||
<!-- Page content -->
|
||
<h1 id="25-summary">2.5 Summary<a class="headerlink" href="#25-summary" title="Permanent link">¶</a></h1>
|
||
<h3 id="1-key-takeaways">1. Key takeaways<a class="headerlink" href="#1-key-takeaways" title="Permanent link">¶</a></h3>
|
||
<p><strong>Evaluating algorithm efficiency</strong></p>
|
||
<ul>
|
||
<li>Time and space efficiency are the two main measures of algorithm quality.</li>
|
||
<li>Practical testing measures efficiency, but cannot easily remove environmental effects and consumes substantial computing resources.</li>
|
||
<li>Complexity analysis avoids those limitations, applies across platforms, and reveals efficiency at different input sizes.</li>
|
||
</ul>
|
||
<p><strong>Time complexity</strong></p>
|
||
<ul>
|
||
<li>Time complexity describes how runtime grows with input size. It is useful for evaluating efficiency, but may not distinguish algorithms accurately for small inputs or equal complexity classes.</li>
|
||
<li>Worst-case time complexity is expressed with big-<span class="arithmatex">\(O\)</span> notation, an asymptotic upper bound describing the growth of the operation count <span class="arithmatex">\(T(n)\)</span> as <span class="arithmatex">\(n\)</span> tends to positive infinity.</li>
|
||
<li>Deriving time complexity takes two steps: count operations, then determine the asymptotic upper bound.</li>
|
||
<li>Common complexities, from slower to faster growth, include <span class="arithmatex">\(O(1)\)</span>, <span class="arithmatex">\(O(\log n)\)</span>, <span class="arithmatex">\(O(n)\)</span>, <span class="arithmatex">\(O(n \log n)\)</span>, <span class="arithmatex">\(O(n^2)\)</span>, <span class="arithmatex">\(O(2^n)\)</span>, and <span class="arithmatex">\(O(n!)\)</span>.</li>
|
||
<li>Some algorithms' complexity depends on the input's arrangement. We distinguish worst-case, best-case, and average-case complexity. Best-case complexity is rarely used because reaching it generally requires strict input conditions.</li>
|
||
<li>Average-case complexity describes performance on random inputs and is closest to typical practical behavior. Calculating it requires an input distribution and its mathematical expectation.</li>
|
||
</ul>
|
||
<p><strong>Space complexity</strong></p>
|
||
<ul>
|
||
<li>Like time complexity, space complexity describes a growth trend: how memory usage increases with input size.</li>
|
||
<li>Memory used during execution includes input, temporary, and output space. Input space is usually excluded from space complexity. Temporary space includes temporary data, stack frames, and instructions; stack frames usually affect complexity only in recursive functions.</li>
|
||
<li>We usually consider worst-case space complexity, measuring memory under the worst input and at the moment of maximum usage.</li>
|
||
<li>Common space complexities, from slower to faster growth, include <span class="arithmatex">\(O(1)\)</span>, <span class="arithmatex">\(O(\log n)\)</span>, <span class="arithmatex">\(O(n)\)</span>, <span class="arithmatex">\(O(n^2)\)</span>, and <span class="arithmatex">\(O(2^n)\)</span>.</li>
|
||
</ul>
|
||
<h3 id="2-q-a">2. Q & A<a class="headerlink" href="#2-q-a" title="Permanent link">¶</a></h3>
|
||
<p><strong>Q</strong>: Does tail recursion have <span class="arithmatex">\(O(1)\)</span> space complexity?</p>
|
||
<p>In theory, tail recursion can be optimized to <span class="arithmatex">\(O(1)\)</span> space. However, most languages, including Java, Python, C++, Go, and C#, do not automatically optimize tail recursion, so its space complexity is usually treated as <span class="arithmatex">\(O(n)\)</span>.</p>
|
||
<p><strong>Q</strong>: What is the difference between a function and a method?</p>
|
||
<p>A <u>function</u> can run independently, with all arguments passed explicitly. A <u>method</u> is associated with an object, receives that object implicitly when called, and can operate on the instance's data.</p>
|
||
<p>Here are examples from several common languages.</p>
|
||
<ul>
|
||
<li>C is procedural and has no built-in object-oriented model, so it has functions only. We can simulate object-oriented programming with structures (<code>struct</code>); functions associated with a structure then act like methods in other languages.</li>
|
||
<li>Java and C# are object-oriented, and executable blocks (methods) are usually part of a class. Static methods behave like functions: they belong to the class and cannot access a particular instance's variables directly.</li>
|
||
<li>C++ and Python support both procedural programming with functions and object-oriented programming with methods.</li>
|
||
</ul>
|
||
<p><strong>Q</strong>: Does the common space complexity chart show absolute memory usage?</p>
|
||
<p>No. It illustrates growth trends rather than absolute amounts of memory.</p>
|
||
<p>For <span class="arithmatex">\(n = 8\)</span>, the plotted values may not match the corresponding functions exactly. Each curve includes a constant term that adjusts it to a visually convenient range.</p>
|
||
<p>In practice, these constant terms are usually unknown, so complexity alone cannot generally identify the best solution for <span class="arithmatex">\(n = 8\)</span>. For <span class="arithmatex">\(n = 8^5\)</span>, the choice is easier because growth rates dominate.</p>
|
||
<p><strong>Q</strong>: Do algorithms sometimes trade time for space, or space for time, depending on the application?</p>
|
||
<p>Most practical applications trade space for time. Database indexes, for example, often use B+ trees or hash indexes, consuming substantial memory to achieve <span class="arithmatex">\(O(\log n)\)</span> or even <span class="arithmatex">\(O(1)\)</span> query time.</p>
|
||
<p>When memory is scarce, the reverse tradeoff may be useful. In embedded development, an engineer might replace a hash table with sequential array search to save memory, accepting slower lookups.</p>
|
||
<!-- Source file information -->
|
||
<!-- Was this page helpful? -->
|
||
<!-- Previous and next pages link -->
|
||
<nav aria-label="Footer" class="md-footer__inner md-grid">
|
||
<!-- Link to previous page -->
|
||
<a aria-label="Previous: 2.4 Space complexity" class="md-footer__link md-footer__link--prev" href="../space_complexity/" rel="prev">
|
||
<div class="md-footer__button md-icon">
|
||
<svg class="lucide lucide-arrow-left" fill="none" stroke="currentColor" stroke-linecap="round" stroke-linejoin="round" stroke-width="2" viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="m12 19-7-7 7-7M19 12H5"></path></svg>
|
||
</div>
|
||
<div class="md-footer__title">
|
||
<span class="md-footer__direction">
|
||
Previous
|
||
</span>
|
||
<div class="md-ellipsis">
|
||
2.4 Space complexity
|
||
</div>
|
||
</div>
|
||
</a>
|
||
<!-- Link to next page -->
|
||
<a aria-label="Next: 2.6 Exercises" class="md-footer__link md-footer__link--next" href="../exercises/" rel="next">
|
||
<div class="md-footer__title">
|
||
<span class="md-footer__direction">
|
||
Next
|
||
</span>
|
||
<div class="md-ellipsis">
|
||
2.6 Exercises
|
||
</div>
|
||
</div>
|
||
<div class="md-footer__button md-icon">
|
||
<svg class="lucide lucide-arrow-right" fill="none" stroke="currentColor" stroke-linecap="round" stroke-linejoin="round" stroke-width="2" viewbox="0 0 24 24" xmlns="http://www.w3.org/2000/svg"><path d="M5 12h14M12 5l7 7-7 7"></path></svg>
|
||
</div>
|
||
</a>
|
||
</nav>
|
||
<!-- Comment system -->
|
||
<!-- Check-in button above comments -->
|
||
<h5 align="center" id="__comments">Share your insights, questions, or suggestions in the comments</h5>
|
||
<!-- Insert generated snippet here -->
|
||
<script async="" crossorigin="anonymous" data-category="Announcements" data-category-id="DIC_kwDOIXtSq84CSZk_" data-emit-metadata="1" data-input-position="top" data-lang="en" data-mapping="pathname" data-reactions-enabled="1" data-repo="krahets/hello-algo" data-repo-id="R_kgDOIXtSqw" data-strict="1" data-theme="light" src="https://giscus.app/client.js">
|
||
</script>
|
||
<!-- Synchronize Giscus theme with palette -->
|
||
<script>
|
||
var giscus = document.querySelector("script[src*=giscus]")
|
||
|
||
function getGiscusTheme() {
|
||
var palette = __md_get("__palette")
|
||
var isDark = palette && typeof palette.color === "object" && palette.color.scheme === "slate"
|
||
return isDark ? "noborder_dark" : "light"
|
||
}
|
||
|
||
/* Set palette on initial load */
|
||
giscus.setAttribute("data-theme", getGiscusTheme())
|
||
|
||
/* The Giscus client creates the iframe asynchronously with an English title. */
|
||
;(function() {
|
||
function labelCommentsFrame() {
|
||
var frame = document.querySelector("iframe.giscus-frame")
|
||
if (!frame) return false
|
||
frame.setAttribute("title", "Comments")
|
||
return true
|
||
}
|
||
if (labelCommentsFrame()) return
|
||
var observer = new MutationObserver(function() {
|
||
if (labelCommentsFrame()) observer.disconnect()
|
||
})
|
||
observer.observe(giscus.parentElement, { childList: true, subtree: true })
|
||
})()
|
||
|
||
/* Register event handlers after documented loaded */
|
||
document.addEventListener("DOMContentLoaded", function() {
|
||
var ref = document.querySelector("[data-md-component=palette]")
|
||
if (!ref) return
|
||
ref.addEventListener("change", function() {
|
||
var theme = getGiscusTheme()
|
||
|
||
/* Instruct Giscus to change theme */
|
||
var frame = document.querySelector(".giscus-frame")
|
||
if (!frame) return
|
||
frame.contentWindow.postMessage(
|
||
{ giscus: { setConfig: { theme } } },
|
||
"https://giscus.app"
|
||
)
|
||
})
|
||
})
|
||
</script>
|
||
</article>
|
||
</div>
|
||
<script>var tabs=__md_get("__tabs");if(Array.isArray(tabs))e:for(var set of document.querySelectorAll(".tabbed-set")){var labels=set.querySelector(".tabbed-labels");for(var tab of tabs)for(var label of labels.getElementsByTagName("label"))if(label.innerText.trim()===tab){var input=document.getElementById(label.htmlFor);input.checked=!0;continue e}}</script>
|
||
<script>var target=document.getElementById(location.hash.slice(1));target&&target.name&&(target.checked=target.name.startsWith("__tabbed_"))</script>
|
||
</div>
|
||
</main>
|
||
<footer class="md-footer">
|
||
<div class="md-footer-meta md-typeset">
|
||
<div class="md-footer-meta__inner md-grid">
|
||
<div class="md-copyright">
|
||
<div class="md-copyright__highlight">
|
||
Copyright © 2026 krahets<br/>The website content is licensed under <a href="https://creativecommons.org/licenses/by-nc-sa/4.0/">CC BY-NC-SA 4.0</a>
|
||
</div>
|
||
</div>
|
||
<div class="md-social">
|
||
<a class="md-social__link" href="https://github.com/krahets" rel="noopener" target="_blank" title="github.com">
|
||
<svg viewbox="0 0 512 512" xmlns="http://www.w3.org/2000/svg"><!--! Font Awesome Free 7.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2026 Fonticons, Inc.--><path d="M173.9 397.4c0 2-2.3 3.6-5.2 3.6-3.3.3-5.6-1.3-5.6-3.6 0-2 2.3-3.6 5.2-3.6 3-.3 5.6 1.3 5.6 3.6m-31.1-4.5c-.7 2 1.3 4.3 4.3 4.9 2.6 1 5.6 0 6.2-2s-1.3-4.3-4.3-5.2c-2.6-.7-5.5.3-6.2 2.3m44.2-1.7c-2.9.7-4.9 2.6-4.6 4.9.3 2 2.9 3.3 5.9 2.6 2.9-.7 4.9-2.6 4.6-4.6-.3-1.9-3-3.2-5.9-2.9M252.8 8C114.1 8 8 113.3 8 252c0 110.9 69.8 205.8 169.5 239.2 12.8 2.3 17.3-5.6 17.3-12.1 0-6.2-.3-40.4-.3-61.4 0 0-70 15-84.7-29.8 0 0-11.4-29.1-27.8-36.6 0 0-22.9-15.7 1.6-15.4 0 0 24.9 2 38.6 25.8 21.9 38.6 58.6 27.5 72.9 20.9 2.3-16 8.8-27.1 16-33.7-55.9-6.2-112.3-14.3-112.3-110.5 0-27.5 7.6-41.3 23.6-58.9-2.6-6.5-11.1-33.3 2.6-67.9 20.9-6.5 69 27 69 27 20-5.6 41.5-8.5 62.8-8.5s42.8 2.9 62.8 8.5c0 0 48.1-33.6 69-27 13.7 34.7 5.2 61.4 2.6 67.9 16 17.7 25.8 31.5 25.8 58.9 0 96.5-58.9 104.2-114.8 110.5 9.2 7.9 17 22.9 17 46.4 0 33.7-.3 75.4-.3 83.6 0 6.5 4.6 14.4 17.3 12.1C436.2 457.8 504 362.9 504 252 504 113.3 391.5 8 252.8 8M105.2 352.9c-1.3 1-1 3.3.7 5.2 1.6 1.6 3.9 2.3 5.2 1 1.3-1 1-3.3-.7-5.2-1.6-1.6-3.9-2.3-5.2-1m-10.8-8.1c-.7 1.3.3 2.9 2.3 3.9 1.6 1 3.6.7 4.3-.7.7-1.3-.3-2.9-2.3-3.9-2-.6-3.6-.3-4.3.7m32.4 35.6c-1.6 1.3-1 4.3 1.3 6.2 2.3 2.3 5.2 2.6 6.5 1 1.3-1.3.7-4.3-1.3-6.2-2.2-2.3-5.2-2.6-6.5-1m-11.4-14.7c-1.6 1-1.6 3.6 0 5.9s4.3 3.3 5.6 2.3c1.6-1.3 1.6-3.9 0-6.2-1.4-2.3-4-3.3-5.6-2" fill="currentColor"></path></svg>
|
||
</a>
|
||
<a class="md-social__link" href="https://twitter.com/krahets" rel="noopener" target="_blank" title="twitter.com">
|
||
<svg viewbox="0 0 448 512" xmlns="http://www.w3.org/2000/svg"><!--! Font Awesome Free 7.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2026 Fonticons, Inc.--><path d="M357.2 48h70.6L273.6 224.2 455 464H313L201.7 318.6 74.5 464H3.8l164.9-188.5L-5.2 48h145.6l100.5 132.9zm-24.8 373.8h39.1L119.1 88h-42z" fill="currentColor"></path></svg>
|
||
</a>
|
||
<a class="md-social__link" href="https://leetcode.cn/u/jyd/" rel="noopener" target="_blank" title="leetcode.cn">
|
||
<svg viewbox="0 0 576 512" xmlns="http://www.w3.org/2000/svg"><!--! Font Awesome Free 7.2.0 by @fontawesome - https://fontawesome.com License - https://fontawesome.com/license/free (Icons: CC BY 4.0, Fonts: SIL OFL 1.1, Code: MIT License) Copyright 2026 Fonticons, Inc.--><path d="M360.8 1.2c-17-4.9-34.7 5-39.6 22l-128 448c-4.9 17 5 34.7 22 39.6s34.7-5 39.6-22l128-448c4.9-17-5-34.7-22-39.6m64.6 136.1c-12.5 12.5-12.5 32.8 0 45.3l73.4 73.4-73.4 73.4c-12.5 12.5-12.5 32.8 0 45.3s32.8 12.5 45.3 0l96-96c12.5-12.5 12.5-32.8 0-45.3l-96-96c-12.5-12.5-32.8-12.5-45.3 0zm-274.7 0c-12.5-12.5-32.8-12.5-45.3 0l-96 96c-12.5 12.5-12.5 32.8 0 45.3l96 96c12.5 12.5 32.8 12.5 45.3 0s12.5-32.8 0-45.3L77.3 256l73.3-73.4c12.5-12.5 12.5-32.8 0-45.3z" fill="currentColor"></path></svg>
|
||
</a>
|
||
</div>
|
||
</div>
|
||
</div>
|
||
</footer>
|
||
</div>
|
||
<div class="md-dialog" data-md-component="dialog">
|
||
<div class="md-dialog__inner md-typeset"></div>
|
||
</div>
|
||
<script id="__config" type="application/json">{"annotate":null,"base":"../../","features":["content.action.edit","content.code.annotate","content.code.copy","content.tabs.link","content.tooltips","navigation.indexes","navigation.tracking","search.highlight","search.share","search.suggest","toc.follow"],"search":"../../assets/javascripts/workers/search.b6b7e04f.min.js","tags":null,"translations":{"clipboard.copied":"Copied to clipboard","clipboard.copy":"Copy to clipboard","search.result.more.one":"1 more on this page","search.result.more.other":"# more on this page","search.result.none":"No matching documents","search.result.one":"1 matching document","search.result.other":"# matching documents","search.result.placeholder":"Type to start searching","search.result.term.missing":"Missing","select.version":"Select version"},"version":null}</script>
|
||
<script src="../../assets/javascripts/bundle.bec5663cf94a73136e878fe1811cbb94591ea317ea949953d97f804d2e051825.min.js"></script>
|
||
<script src="../../javascripts/mathjax.js"></script>
|
||
<script src="https://cdnjs.cloudflare.com/ajax/libs/mathjax/3.2.2/es5/tex-mml-chtml.min.js"></script>
|
||
<script src="../../javascripts/animation_player.js"></script>
|
||
</body>
|
||
</html> |