Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commitb65a992

Browse files
committed
Update READMEs.
1 parente53f5f9 commitb65a992

File tree

2 files changed

+30
-24
lines changed

2 files changed

+30
-24
lines changed

‎README.md

Lines changed: 22 additions & 22 deletions
Original file line numberDiff line numberDiff line change
@@ -215,28 +215,28 @@ Below is the list of some of the most used Big O notations and their performance
215215

216216
###Data Structure Operations Complexity
217217

218-
| Data Structure| Access| Search| Insertion| Deletion| Comments|
219-
| -----------------------| :-------:| :-------:| :-------:| :-------:| :--------|
220-
|**Array**|1|n|n|n||
221-
|**Stack**|n|n|1|1||
222-
|**Queue**|n|n|1|1||
223-
|**Linked List**|n|n|1|1||
224-
|**Hash Table**| -| n|n|n| In case of perfect hash function costs would be O(1)|
225-
|**Binary Search Tree**|n|n|n|n| In case of balanced tree costs would be O(log(n))|
226-
|**B-Tree**| log(n)| log(n)| log(n)| log(n)||
227-
|**Red-Black Tree**| log(n)| log(n)| log(n)| log(n)||
228-
|**AVL Tree**| log(n)| log(n)| log(n)| log(n)||
218+
| Data Structure| Access| Search| Insertion| Deletion| Comments|
219+
| -----------------------| :---------:| :---------:| :---------:| :---------:| :--------|
220+
|**Array**|`1`|`n`|`n`|`n`||
221+
|**Stack**|`n`|`n`|`1`|`1`||
222+
|**Queue**|`n`|`n`|`1`|`1`||
223+
|**Linked List**|`n`|`n`|`1`|`1`||
224+
|**Hash Table**| -|`n`|`n`|`n`| In case of perfect hash function costs would be`O(1)`|
225+
|**Binary Search Tree**|`n`|`n`|`n`|`n`| In case of balanced tree costs would be`O(log(n))`|
226+
|**B-Tree**|`log(n)`|`log(n)`|`log(n)`|`log(n)`||
227+
|**Red-Black Tree**|`log(n)`|`log(n)`|`log(n)`|`log(n)`||
228+
|**AVL Tree**|`log(n)`|`log(n)`|`log(n)`|`log(n)`||
229229

230230
###Array Sorting Algorithms Complexity
231231

232-
| Name| Best| Average| Worst| Memory| Stable| Comments|
233-
| ---------------------| :-------:| :-------:| :-----------:| :-------:| :-------:| :--------|
234-
|**Bubble sort**|n| n^2| n^2|1| Yes||
235-
|**Insertion sort**|n| n^2| n^2|1| Yes||
236-
|**Selection sort**| n^2| n^2| n^2|1| No||
237-
|**Heap sort**| n log(n)| n log(n)| n log(n)|1| No||
238-
|**Merge sort**| n log(n)| n log(n)| n log(n)|n| Yes||
239-
|**Quick sort**| n log(n)| n log(n)| n^2| log(n)| No||
240-
|**Shell sort**| n log(n)| depends on gap sequence| n (log(n))^2|1| No||
241-
|**Counting sort**| n + r| n + r| n + r| n + r| Yes|r - biggest number in array|
242-
|**Radix sort**| n * k| n * k| n * k| n + k| Yes| k - length of longest key|
232+
| Name| Best| Average| Worst| Memory| Stable| Comments|
233+
| ---------------------| :---------:| :---------:| :-------------:| :---------:| :-------:| :--------|
234+
|**Bubble sort**|`n`|`n^2`|`n^2`|`1`| Yes||
235+
|**Insertion sort**|`n`|`n^2`|`n^2`|`1`| Yes||
236+
|**Selection sort**|`n^2`|`n^2`|`n^2`|`1`| No||
237+
|**Heap sort**|`n log(n)`|`n log(n)`|`n log(n)`|`1`| No||
238+
|**Merge sort**|`n log(n)`|`n log(n)`|`n log(n)`|`n`| Yes||
239+
|**Quick sort**|`n log(n)`|`n log(n)`|`n^2`|`log(n)`| No||
240+
|**Shell sort**|`n log(n)`| depends on gap sequence|`n (log(n))^2`|`1`| No||
241+
|**Counting sort**|`n + r`|`n + r`|`n + r`|`n + r`| Yes|`r` - biggest number in array|
242+
|**Radix sort**|`n * k`|`n * k`|`n * k`|`n + k`| Yes|`k` - length of longest key|

‎src/algorithms/sorting/bubble-sort/README.md

Lines changed: 8 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -11,9 +11,15 @@ are needed, which indicates that the list is sorted.
1111

1212
##Complexity
1313

14-
######time: worst_O_(_n_<sup>2</sup>), best_O_(_n_), average_O_(_n_<sup>2</sup>)
14+
Time
1515

16-
######space: worst_O_(1) auxiliary
16+
- worst_O_(_n_<sup>2</sup>),
17+
- best_O_(_n_),
18+
- average_O_(_n_<sup>2</sup>)
19+
20+
Space
21+
22+
worst_O_(1) auxiliary
1723

1824

1925
##References

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp