요약 (2)

Legend

Excellent Good Fair Bad Horrible

자료구조별 시간복잡도 및 공간복잡도

자료구조 시간 복잡도 공간복잡도
  Average Worst Worst
  Access Search Insertion Deletion Access Search Insertion Deletion  
Array O(1) O(n) O(n) O(n) O(1) O(n) O(n) O(n) O(n)
Stack O(n) O(n) O(1) O(1) O(n) O(n) O(1) O(1) O(n)
Singly-Linked List O(n) O(n) O(1) O(1) O(n) O(n) O(1) O(1) O(n)
Doubly-Linked List O(n) O(n) O(1) O(1) O(n) O(n) O(1) O(1) O(n)
Skip List O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n) O(n) O(n) O(n) O(n log(n))
Hash Table - O(1) O(1) O(1) - O(n) O(n) O(n) O(n)
Binary Search Tree O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n) O(n) O(n) O(n) O(n)
Cartesian Tree - O(log(n)) O(log(n)) O(log(n)) - O(n) O(n) O(n) O(n)
B-Tree O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)
Red-Black Tree O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)
Splay Tree - O(log(n)) O(log(n)) O(log(n)) - O(log(n)) O(log(n)) O(log(n)) O(n)
AVL Tree O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(n)

정렬 알고리즘 시간복잡도 및 공간복잡도

알고리즘 시간복잡도 공간복잡도
  Best Average Worst Worst
Quicksort O(n log(n)) O(n log(n)) O(n^2) O(log(n))
Mergesort O(n log(n)) O(n log(n)) O(n log(n)) O(n)
Timsort O(n) O(n log(n)) O(n log(n)) O(n)
Heapsort O(n log(n)) O(n log(n)) O(n log(n)) O(1)
Bubble Sort O(n) O(n^2) O(n^2) O(1)
Insertion Sort O(n) O(n^2) O(n^2) O(1)
Selection Sort O(n^2) O(n^2) O(n^2) O(1)
Shell Sort O(n) O((nlog(n))^2) O((nlog(n))^2) O(1)
Bucket Sort O(n+k) O(n+k) O(n^2) O(n)
Radix Sort O(nk) O(nk) O(nk) O(n+k)

Graph Operations

Node / Edge Management Storage Add Vertex Add Edge Remove Vertex Remove Edge Query
Adjacency list O(|V|+|E|) O(1) O(1) O(|V| + |E|) O(|E|) O(|V|)
Incidence list O(|V|+|E|) O(1) O(1) O(|E|) O(|E|) O(|E|)
Adjacency matrix O(|V|^2) O(|V|^2) O(1) O(|V|^2) O(1) O(1)
Incidence matrix O(|V| ⋅ |E|) O(|V| ⋅ |E|) O(|V| ⋅ |E|) O(|V| ⋅ |E|) O(|V| ⋅ |E|) O(|E|)

Heap Operations

Type 시간복잡도
  Heapify Find Max Extract Max Increase Key Insert Delete Merge
Linked List (sorted) - O(1) O(1) O(n) O(n) O(1) O(m+n)
Linked List (unsorted) - O(n) O(n) O(1) O(1) O(1) O(1)
Binary Heap O(n) O(1) O(log(n)) O(log(n)) O(log(n)) O(log(n)) O(m+n)
Binomial Heap - O(1) O(log(n)) O(log(n)) O(1) O(log(n)) O(log(n))
Fibonacci Heap - O(1) O(log(n)) O(1) O(1) O(log(n)) O(1)

 

💻 Programming/Linux

vim 명령어 ( vi commands )

< The list of Vim commands >

Working with files
Vim commandAction
:e filenameOpen a new file. You can use the Tab key for automatic file name completion, just like at the shell command prompt.
:w filenameSave changes to a file. If you don't specify a file name, Vim saves as the file name you were editing. For saving the file under a different name, specify the file name.
:qQuit Vim. If you have unsaved changes, Vim refuses to exit.
:q!Exit Vim without saving changes.
:wqWrite the file and exit.
:xAlmost the same as :wq, write the file and exit if you've made changes to the file. If you haven't made any changes to the file, Vim exits without writing the file.
These Vim commands and keys work both in command mode and visual mode.
Vim commandAction
j or Up ArrowMove the cursor up one line.
k or Down ArrowDown one line.
h or Left ArrowLeft one character.
l or Right ArrowRight one character.
eTo the end of a word.
ETo the end of a whitespace-delimited word.
bTo the beginning of a word.
BTo the beginning of a whitespace-delimited word.
0To the beginning of a line.
^To the first non-whitespace character of a line.
$To the end of a line.
HTo the first line of the screen.
MTo the middle line of the screen.
LTo the the last line of the screen.
:nJump to line number n. For example, to jump to line 42, you'd type :42
Inserting and overwriting text
Vim commandAction
iInsert before cursor.
IInsert to the start of the current line.
aAppend after cursor.
AAppend to the end of the current line.
oOpen a new line below and insert.
OOpen a new line above and insert.
CChange the rest of the current line.
rOverwrite one character. After overwriting the single character, go back to command mode.
REnter insert mode but replace characters rather than inserting.
The ESC keyExit insert/overwrite mode and go back to command mode.
Deleting text
Vim commandAction
xDelete characters under the cursor.
XDelete characters before the cursor.
dd or :dDelete the current line.
Entering visual mode
Vim commandAction
vStart highlighting characters. Use the normal movement keys and commands to select text for highlighting.
VStart highlighting lines.
The ESC keyExit visual mode and return to command mode.
Editing blocks of text
Note: the Vim commands marked with (V) work in visual mode, when you've selected some text. The other commands work in the command mode, when you haven't selected any text.
Vim commandAction
~Change the case of characters. This works both in visual and command mode. In visual mode, change the case of highlighted characters. In command mode, change the case of the character uder cursor.
> (V)Shift right (indent).
< (V)Shift left (de-indent).
c (V)Change the highlighted text.
y (V)Yank the highlighted text. In Windows terms, "copy the selected text to clipboard."
d (V)Delete the highlighted text. In Windows terms, "cut the selected text to clipboard."
yy or :y or YYank the current line. You don't need to highlight it first.
dd or :dDelete the current line. Again, you don't need to highlight it first.
pPut the text you yanked or deleted. In Windows terms, "paste the contents of the clipboard". Put characters after the cursor. Put lines below the current line.
PPut characters before the cursor. Put lines above the current line.
Undo and redo
Vim commandAction
uUndo the last action.
UUndo all the latest changes that were made to the current line.
Ctrl + rRedo.
Vim commandAction
/patternSearch the file for pattern.
nScan for next search match in the same direction.
NScan for next search match but opposite direction.
Replace
Vim commandAction
:rs/foo/bar/aSubstitute foo with bar. r determines the range and a determines the arguments.
The range (r) can be
nothingWork on current line only.
numberWork on the line whose number you give.
%The whole file.
Arguments (a) can be
gReplace all occurrences in the line. Without this, Vim replaces only the first occurrences in each line.
iIgnore case for the search pattern.
IDon't ignore case.
cConfirm each substitution. You can type y to substitute this match, n to skip this match, a to substitute this and all the remaining matches ("Yes to all"), and q to quit substitution.
Examples
:452s/foo/bar/Replace the first occurrence of the word foo with bar on line number 452.
:s/foo/bar/gReplace every occurrence of the word foo with bar on current line.
:%s/foo/bar/gReplace every occurrence of the word foo with bar in the whole file.
:%s/foo/bar/giThe same as above, but ignore the case of the pattern you want to substitute. This replaces foo, FOO, Foo, and so on.
:%s/foo/bar/gcConfirm every substitution.
:%s/foo/bar/cFor each line on the file, replace the first occurrence of foo with bar and confirm every substitution.

 

 

 

 

Reference:

http://www.tuxfiles.org/linuxhelp/vimcheat.html