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

Commit390c490

Browse files
committed
Everything
0 parents  commit390c490

26 files changed

+802
-0
lines changed

‎.gitignore

Lines changed: 51 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,51 @@
1+
# Created by .ignore support plugin (hsz.mobi)
2+
### Node template
3+
# Logs
4+
logs
5+
*.log
6+
npm-debug.log*
7+
8+
# Runtime data
9+
pids
10+
*.pid
11+
*.seed
12+
*.pid.lock
13+
14+
# Directory for instrumented libs generated by jscoverage/JSCover
15+
lib-cov
16+
17+
# Coverage directory used by tools like istanbul
18+
coverage
19+
20+
# nyc test coverage
21+
.nyc_output
22+
23+
# Grunt intermediate storage (http://gruntjs.com/creating-plugins#storing-task-files)
24+
.grunt
25+
26+
# node-waf configuration
27+
.lock-wscript
28+
29+
# Compiled binary addons (http://nodejs.org/api/addons.html)
30+
build/Release
31+
32+
# Dependency directories
33+
node_modules
34+
jspm_packages
35+
36+
# Optional npm cache directory
37+
.npm
38+
39+
# Optional eslint cache
40+
.eslintcache
41+
42+
# Optional REPL history
43+
.node_repl_history
44+
45+
# Output of 'npm pack'
46+
*.tgz
47+
48+
# Yarn Integrity file
49+
.yarn-integrity
50+
51+

‎package.json

Lines changed: 15 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,15 @@
1+
{
2+
"name":"typescript-algorithms",
3+
"version":"1.0.0",
4+
"description":"",
5+
"main":"index.js",
6+
"scripts": {
7+
"test":"echo\"Error: no test specified\" && exit 1"
8+
},
9+
"author":"",
10+
"license":"ISC",
11+
"dependencies": {
12+
"benchmark":"^2.1.2",
13+
"chart":"github:jstrace/chart"
14+
}
15+
}

‎src/big-o/o-1.js

Lines changed: 22 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,22 @@
1+
import{generateArray,runBenchmark}from'../helpers';
2+
letarrays=[
3+
generateArray(10),
4+
generateArray(20),
5+
generateArray(30),
6+
generateArray(40),
7+
generateArray(50),
8+
generateArray(60),
9+
generateArray(70),
10+
generateArray(80),
11+
generateArray(90),
12+
generateArray(100)
13+
];
14+
//O(1)
15+
functionbiggerThan(numbers,biggerThan){
16+
returnnumbers.length>biggerThan;
17+
}
18+
constsuite=newBenchmark.Suite('O(1) will always execute in the same time regardless of the input size:');
19+
for(leti=0;i<arrays.length;i++){
20+
suite.add(`${arrays[i].length}`,()=>biggerThan(arrays[i],1));
21+
}
22+
runBenchmark(suite);

‎src/big-o/o-1.ts

Lines changed: 26 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,26 @@
1+
importBenchmark= require('benchmark');
2+
import{generateArray,runBenchmark}from'../helpers';
3+
4+
letarrays=[
5+
generateArray(10),
6+
generateArray(20),
7+
generateArray(30),
8+
generateArray(40),
9+
generateArray(50),
10+
generateArray(60),
11+
generateArray(70),
12+
generateArray(80),
13+
generateArray(90),
14+
generateArray(100)
15+
];
16+
17+
//O(1)
18+
functionbiggerThan(numbers:Array<number>,biggerThan:number):boolean{
19+
returnnumbers.length>biggerThan;
20+
}
21+
22+
constsuite=newBenchmark.Suite('O(1) will always execute in the same time regardless of the input size:');
23+
for(leti=0;i<arrays.length;i++){
24+
suite.add(`${arrays[i].length}`,()=>biggerThan(arrays[i],1));
25+
}
26+
runBenchmark(suite);

‎src/big-o/o-2n.js

Lines changed: 16 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,16 @@
1+
import{runBenchmark}from'../helpers';
2+
letarrays=[
3+
1,2,3,4,5,6
4+
];
5+
//O(2n)
6+
functionfibonacci(num){
7+
if(num<=1){
8+
returnnum;
9+
}
10+
returnfibonacci(num-2)+fibonacci(num-1);
11+
}
12+
constsuite=newBenchmark.Suite('O(2^n) will perform in exponentially in proportion to size of the data set');
13+
for(leti=0;i<arrays.length;i++){
14+
suite.add(`${arrays[i]}`,()=>fibonacci(arrays[i]));
15+
}
16+
runBenchmark(suite);

‎src/big-o/o-2n.ts

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
importBenchmark= require('benchmark');
2+
import{runBenchmark}from'../helpers';
3+
4+
letarrays=[
5+
1,2,3,4,5,6
6+
];
7+
8+
//O(2n)
9+
functionfibonacci(num:number):number{
10+
if(num<=1){
11+
returnnum;
12+
}
13+
returnfibonacci(num-2)+fibonacci(num-1);
14+
}
15+
16+
constsuite=newBenchmark.Suite('O(2^n) will perform in exponentially in proportion to size of the data set');
17+
for(leti=0;i<arrays.length;i++){
18+
suite.add(`${arrays[i]}`,()=>fibonacci(arrays[i]));
19+
}
20+
21+
runBenchmark(suite);

‎src/big-o/o-logn.js

Lines changed: 21 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,21 @@
1+
import{generateArray,runBenchmark}from'../helpers';
2+
importbinarySeachfrom'../binary-search/iterative';
3+
letarrays=[
4+
generateArray(1000),
5+
generateArray(2000),
6+
generateArray(3000),
7+
generateArray(4000),
8+
generateArray(5000),
9+
generateArray(6000),
10+
generateArray(7000),
11+
generateArray(8000),
12+
generateArray(9000),
13+
generateArray(10000)
14+
];
15+
//O(log(2, n)
16+
constsuite=newBenchmark.Suite('O(2, n) will perform logarithmically in proportion to the size of the data set:');
17+
for(leti=0;i<arrays.length;i++){
18+
lettoFind=arrays[i][Math.round(arrays[i].length*0.3)];
19+
suite.add(`${arrays[i].length}`,()=>binarySeach(toFind,arrays[i]));
20+
}
21+
runBenchmark(suite);

‎src/big-o/o-logn.ts

Lines changed: 23 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,23 @@
1+
importBenchmark= require('benchmark');
2+
import{generateArray,runBenchmark}from'../helpers';
3+
importbinarySeachfrom'../binary-search/iterative';
4+
5+
letarrays=[
6+
generateArray(1000),
7+
generateArray(2000),
8+
generateArray(3000),
9+
generateArray(4000),
10+
generateArray(5000),
11+
generateArray(6000),
12+
generateArray(7000),
13+
generateArray(8000),
14+
generateArray(9000),
15+
generateArray(10000)
16+
];
17+
//O(log(2, n)
18+
constsuite=newBenchmark.Suite('O(2, n) will perform logarithmically in proportion to the size of the data set:');
19+
for(leti=0;i<arrays.length;i++){
20+
lettoFind=arrays[i][Math.round(arrays[i].length*0.3)];
21+
suite.add(`${arrays[i].length}`,()=>binarySeach(toFind,arrays[i]));
22+
}
23+
runBenchmark(suite);

‎src/big-o/o-n.js

Lines changed: 27 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,27 @@
1+
import{generateArray,runBenchmark}from'../helpers';
2+
letarrays=[
3+
generateArray(100),
4+
generateArray(200),
5+
generateArray(300),
6+
generateArray(400),
7+
generateArray(500),
8+
generateArray(600),
9+
generateArray(700),
10+
generateArray(800),
11+
generateArray(900),
12+
generateArray(1000)
13+
];
14+
//O(n)
15+
functionsearch(numbers,toFind){
16+
for(letiofnumbers){
17+
if(toFind===i){
18+
returni;
19+
}
20+
}
21+
return-1;
22+
}
23+
constsuite=newBenchmark.Suite('O(n) will perform linearly in proportion to the size of the data set:');
24+
for(leti=0;i<arrays.length;i++){
25+
suite.add(`${arrays[i].length}`,()=>search(arrays[i],arrays[i][arrays[i].length-1]));
26+
}
27+
runBenchmark(suite);

‎src/big-o/o-n.ts

Lines changed: 30 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,30 @@
1+
importBenchmark= require('benchmark');
2+
import{generateArray,runBenchmark}from'../helpers';
3+
4+
letarrays=[
5+
generateArray(100),
6+
generateArray(200),
7+
generateArray(300),
8+
generateArray(400),
9+
generateArray(500),
10+
generateArray(600),
11+
generateArray(700),
12+
generateArray(800),
13+
generateArray(900),
14+
generateArray(1000)
15+
];
16+
//O(n)
17+
functionsearch(numbers:Array<number>,toFind:number):number{
18+
for(letiofnumbers){
19+
if(toFind===i){
20+
returni;
21+
}
22+
}
23+
return-1;
24+
}
25+
26+
constsuite=newBenchmark.Suite('O(n) will perform linearly in proportion to the size of the data set:');
27+
for(leti=0;i<arrays.length;i++){
28+
suite.add(`${arrays[i].length}`,()=>search(arrays[i],arrays[i][arrays[i].length-1]));
29+
}
30+
runBenchmark(suite);

‎src/big-o/o-n2.js

Lines changed: 29 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,29 @@
1+
import{generateArray,runBenchmark}from'../helpers';
2+
letarrays=[
3+
generateArray(11),
4+
generateArray(21),
5+
generateArray(31),
6+
generateArray(41),
7+
generateArray(51),
8+
generateArray(61),
9+
generateArray(71),
10+
generateArray(81),
11+
generateArray(91)
12+
];
13+
//O(n^2)
14+
functionsearchForProduct(numbers,moreNumbers,toFind){
15+
for(letiofnumbers){
16+
for(letjofmoreNumbers){
17+
if(i*j===toFind){
18+
return[i,j];
19+
}
20+
}
21+
}
22+
return[-1,-1];
23+
}
24+
constsuite=newBenchmark.Suite('O(n^2) will perform in proportion to the square of the data set');
25+
for(leti=0;i<arrays.length;i++){
26+
lettoFind=arrays[i][arrays[i].length-1]*arrays[i][arrays[i].length-1];
27+
suite.add(`${arrays[i].length}`,()=>searchForProduct(arrays[i],arrays[i].slice(0),toFind));
28+
}
29+
runBenchmark(suite);

‎src/big-o/o-n2.ts

Lines changed: 33 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,33 @@
1+
importBenchmark= require('benchmark');
2+
import{generateArray,runBenchmark}from'../helpers';
3+
4+
letarrays=[
5+
generateArray(11),
6+
generateArray(21),
7+
generateArray(31),
8+
generateArray(41),
9+
generateArray(51),
10+
generateArray(61),
11+
generateArray(71),
12+
generateArray(81),
13+
generateArray(91)
14+
];
15+
16+
//O(n^2)
17+
functionsearchForProduct(numbers:Array<number>,moreNumbers:Array<number>,toFind:number):Array<number>{
18+
for(letiofnumbers){
19+
for(letjofmoreNumbers){
20+
if(i*j===toFind){
21+
return[i,j];
22+
}
23+
}
24+
}
25+
return[-1,-1];
26+
}
27+
28+
constsuite=newBenchmark.Suite('O(n^2) will perform in proportion to the square of the data set');
29+
for(leti=0;i<arrays.length;i++){
30+
lettoFind=arrays[i][arrays[i].length-1]*arrays[i][arrays[i].length-1];
31+
suite.add(`${arrays[i].length}`,()=>searchForProduct(arrays[i],arrays[i].slice(0),toFind));
32+
}
33+
runBenchmark(suite);

‎src/binary-search/iterative.js

Lines changed: 36 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,36 @@
1+
'use strict';
2+
import{runBenchmark}from'../helpers';
3+
import{generateArray}from'./random';
4+
letarrays=[
5+
generateArray(1000,1,1000),
6+
generateArray(2000,1,2000),
7+
generateArray(3000,1,3000),
8+
generateArray(4000,1,4000),
9+
generateArray(5000,1,5000)
10+
];
11+
exportdefaultfunctionbinarySearch(key,arr,sorted=false){
12+
if(!sorted){
13+
arr.sort((a,b)=>a-b);
14+
}
15+
letlo=0;
16+
lethi=arr.length-1;
17+
while(lo<=hi){
18+
letmid=lo+(Math.floor((hi-lo)/2));
19+
if(key<arr[mid]){
20+
hi=mid-1;
21+
}
22+
elseif(key>arr[mid]){
23+
lo=mid+1;
24+
}
25+
else{
26+
returnmid;
27+
}
28+
}
29+
return-1;
30+
}
31+
constsuite=newBenchmark.Suite('Binary search (iterative implementation)');
32+
for(leti=0;i<arrays.length;i++){
33+
lettoFind=arrays[i][Math.floor(arrays[i].length*0.3)];
34+
suite.add(`${arrays[i].length}`,()=>binarySearch(toFind,arrays[i],true));
35+
}
36+
runBenchmark(suite);

0 commit comments

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