Hi, I'm an a computer sience course and we had there got an
executable of witch code we don't know, our task is then to determine the complexity of three different algorithm contained by the executable. To do some test's I wrote a bash script:
CODE
#!/bin/bash
# Varibles that the script could be easy to change and configure
save='tee -a test_data.txt'
filename='./algorithms_linux'
algorithm='-1'
number_of_elements='1'
number_of_times='1'
# Change the text to some cool color and clear the terminal
tput setaf 2
clear
# Write an welcome message and show how powerful the system is
echo
echo "Welcome to Roberts test program for lab2 in DOA"
echo "Machineinfo:" $black
echo
u n a m e -a
echo
# Change terminalcolor for test 1 to red, then loop from 1 to 200 in steps of 5. Output from executable
# is formatet with the program sed so that "Running algorithm" does not have to be printed, the output
# is also written to a file defined in the varible $save. number_of_elements is also changed to a tested
# value so that the output will be good enough to determine the time complexity
tput setaf 1
echo "First lets try algoritm number 1"
echo
algorithm='-1'
number_of_elements='1'
for i in {1..200..5}
do
$filename $algorithm $number_of_elements $number_of_times | sed 1d | $save
number_of_elements=$((number_of_elements+700000))
done
# Change terminalcolor for test 2 to orange and change the varible $algorithm to 2 and reset number_of_elements,
# then loop from 1 to 200 in steps of 5. Output from executable is formatet with the program sed so that "Running algorithm"
# does not have to be printed, the output is also written to a file defined in the varible $save. number_of_elements is also
# changed to a tested value so that the output will be good enough to determine the time complexity
tput setaf 3
echo
echo "Then try algoritm number 2"
echo
algorithm='-2'
number_of_elements='1'
for i in {1..200..5}
do
$filename $algorithm $number_of_elements $number_of_times | sed 1d | $save
number_of_elements=$((number_of_elements+40))
done
# Change terminalcolor for test 3 to blue and change the varible $algorithm to 3 and reset number_of_elements,
# then loop from 1 to 25 in steps of 1. Output from executable is formatet with the program sed so that "Running algorithm"
# does not have to be printed, the output is also written to a file defined in the varible $save. number_of_elements is also
# changed to a tested value so that the output will be good enough to determine the time complexity
tput setaf 4
echo
echo "Then try algoritm number 3"
echo
algorithm='-3'
number_of_elements='1'
for i in {1..25..1}
do
$filename $algorithm $number_of_elements $number_of_times | sed 1d | $save
number_of_elements=$((number_of_elements+1))
done
# Reset the terminal
tput sgr0
With this I get some nice output about the algorithms and I can generly see how they differ in complexity:
(The first is the number of elements and the secund is the time in seconds)
CODE
Welcome to Roberts test program for lab2 in DOA
Machineinfo:
Linux eagle 2.6.30-ARCH #1 SMP PREEMPT Wed Sep 9 12:37:32 UTC 2009 i686 AMD Athlon(tm) 64 X2 Dual Core Processor 5000+ AuthenticAMD GNU/Linux
First lets try algoritm number 1
1 0.0000
700001 0.8066
1400001 1.6243
2100001 2.5877
2800001 3.4399
3500001 4.3160
4200001 5.2169
4900001 6.2160
5600001 7.3683
6300001 8.0327
7000001 9.0217
7700001 9.8250
8400001 10.6528
9100001 11.7470
9800001 12.5368
10500001 13.4444
11200001 14.4780
11900001 15.3136
12600001 16.5633
13300001 17.4950
14000001 18.4652
14700001 19.2221
15400001 20.1913
16100001 21.6676
16800001 22.1115
17500001 23.2204
18200001 24.7632
18900001 25.2189
19600001 26.5832
20300001 27.0986
21000001 28.1533
21700001 28.9992
22400001 30.6415
23100001 31.0274
23800001 31.9267
24500001 32.9072
25200001 34.0189
25900001 35.7446
26600001 35.8853
27300001 37.7043
Then try algoritm number 2
1 0.0000
41 0.0028
81 0.0086
121 0.0526
161 0.0679
201 0.1438
241 0.2533
281 0.4443
321 0.7227
361 0.9385
401 1.4250
441 1.5249
481 1.9342
521 2.3539
561 2.8966
601 3.6672
641 4.4277
681 5.2379
721 6.3040
761 7.0308
801 8.5049
841 9.7524
881 10.9308
921 13.4779
961 14.7997
1001 16.0273
1041 18.7196
1081 21.0164
1121 22.3883
1161 26.0810
1201 29.9030
1241 32.1204
1281 34.7626
1321 38.4543
1361 41.3915
1401 46.6086
1441 51.9416
1481 53.3268
1521 56.4677
1561 61.0293
Then try algoritm number 3
1 0.0001
2 0.0001
3 0.0002
4 0.0004
5 0.0008
6 0.0016
7 0.0032
8 0.0063
9 0.0125
10 0.0253
11 0.0563
12 0.1043
13 0.2075
14 0.4228
15 0.8198
16 1.6608
17 3.2856
18 6.9580
19 13.1062
20 25.5138
21 52.7667
22 102.6420
23 205.0299
24 408.8173
25 871.8388
So far so good!
But now comes my problems, I'm not sure how to calculate "Big O" and how to show it... I have done a plot on my calculator and also a diagram in openoffice and I can see some of the curve how fast it grows, but how do I determine the complexity? To just put in some N^2 N^3 log(n) graph did not go that well.. hehe
I know it should be done in some fancy way but I have a little hard time doing it, so if anyone would help me out some I would appreciate it!
Regards, Robert
EDIT: To make this clear I don't have any code for this just an executable
This post has been edited by Scorpiion: 30 Sep, 2009 - 11:59 AM
Forum Index:
Programming Help |
C and C++ |
VB6 |
Java |
VB.NET |
C# |
ASP.NET |
PHP |
ColdFusion |
Perl and Python |
Ruby |
Databases |
Other Languages |
Game Programming |
Mobile Development |
Software Development |
Computer Science |
Industry News |
Programming Tutorials |
C++ Tutorials |
Visual Basic Tutorials |
Java Tutorials |
VB.NET Tutorials |
C# Tutorials |
Linux Tutorials |
PHP Tutorials |
ColdFusion Tutorials |
Windows Tutorials |
HTML/JavaScript Tutorials |
CSS Tutorials |
Flash Tutorials |
Web Promotion Tutorials |
Graphic Design & Photoshop Tutorials |
Software Development Tutorials |
Database Tutorials |
Other Language Tutorials |
ASP.NET Tutorials |
Game Programming Tutorials |
WPF & Silverlight Tutorials |
30 Sep, 2009 - 11:02 AM
| 
