New Topic/Question
Reply
Posted 30 September 2009 - 12:02 PM
#!/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)
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 September 2009 - 12:59 PM
MultiQuote
| 