www.fatihkabakci.com

Personal Website and Computer Science TUR EN

YAZILIMIN HESAPLAMA KARMASIKLIGI

Last update: 5/19/2015 2:40:00 PM

Yazan:Fatih KABAKCI

Bir yazılımın hesaplama karmaşıklığı(computational complexity), bir algoritma, prosedür, fonksiyon veya bir metodun işletilmesi için harcanan CPU zamanı(time) ve/veya kaplanan bellek(memory) ihtiyacını belirten ve aynı zamanda ilgili algoritmanın ölçeklenebilirliğini(scability) ifade eden bir kavramdır. Bir algoritmanın performansı(performance), algoritmanın çalışması için harcanan CPU zamanı ile ihtiyaç duyduğu bellek alanı ile ilgilidir. Bir algoritmanın ölçeklenebilirliği(scalability) ise, problemin boyutunun artması ile algoritma çözümü ve anlamlandırılmasının ne derece değiştiği ile ilgilidir.

Genel olarak Bilgisayar Bilimlerinde bir algoritmanın performans ve karmaşıklık analizi yapılırken CPU ve bellek konusu gözetilir. Bunun daha açılmış hali kimi yayınlarda, CPU zamanı, disk alanı, hafıza alanı ve network kullanımı olarak bahsedilir.

Bir algoritma analizinde genel olarak aşağıdaki 3 senaryo sorgulanır.

En kötü durum(worst case): Bir kod parçasının işletilmesi sırasında harcanan maksimum zaman ve/veya kaplanan maksimum bellek ihtiyacını gösterir.
En iyi durum(best case): Bir kod parçasının işletilmesi sırasında harcanan minimum zaman ve/veya kaplanan minimum bellek ihtiyacını gösterir.
Ortalama durum(average case): Bir kod parçasının işletilmesi sırasında harcanan ortalama zaman ve/veya kaplanan ortalama bellek ihtiyacını gösterir.

Örneğin Doğrusal Arama(Linear Search) algoritmasının performansına bakarak aşağıdaki dizideki bir elemanı bulmaya çalışalım.

örnek olarak 6 elemanlı, 8 12 90 13 2 7 sayılarından oluşan bir dizimiz olsun. Doğrusal arama algoritmasına göre bu sayılar arasında bulunacak bir eleman için en kötü durum; elemanın en sonda bulunması veya hiç dizide olmamasıdır. Bu durumda en çok 6 arama yapılacağı için n=6 worst case durumu oluşur [ O(n) ]. en iyi durum; elemanın en başta bulunmasıdır. Bu durumda 1 arama yapılacağı için n=1 best case durumu oluşur [ O(1) ]. ortalama durum; elemanın bir çok kez aramada ortalama olarak kaç adımda bulunacağını gösterir. Bu durumda her bir elemanın eşit derece de aranması n=6/2=3 average case durumu oluşur[ O(n/2) ]. Aynı şekilde kaplama alanına bakıldığında dizi uzunluğu sabit olduğu için bu algoritma da tüm senaryolar eşittir.

Yazılımın hesaplama karmaşıklığı belirlenirken harcanan CPU zamanı bazı kod ifadelerine göre değişik şekillerde belirlenir. Aşağıda farklı kod ifadeleri ile hesaplama örnekleri verilmektedir.

Sıralı İfadeler(Sequence of Statements)

Sıralı ifadeler, sıralı olarak ard arda işletilen kodlara verilen isimdir. Her bir ifadenin CPU zamanı doğrusal olarak toplanarak ilgili algoritma ya da kod parçacığının hesaplama karmaşıklığı ortaya çıkarılır.

statement 1;
statement 2;
...
statement n;

total time = time(statement 1) + time(statement 2) + ... + time(statement n)

Elde edilen toplam zaman sabit olduğu için O(1) ile ifade edilir.

Dallanmalar - Kontrol Deyimleri(If-Then-Else)

Dallanmalar, farklı durumlarda farklı kollardan devam eden kod parçalarına verilen isimdir. Her bir dal parçasının CPU zamanı ayrı ayrı hesaplanarak maksimum değer elde edilir. Bu değer en kötü durumu(worst case) ihtiva eden hesaplama karmaşıklığını verir.

if (cond) then
block 1 (sequence of statements)
else
block 2 (sequence of statements)
end if;

max(time(block 1), time(block 2))

Örneğin elde edilen maksimum zaman block1 için O(1), block2 için O(n) olursa, algoritmanın hesaplama karmaşıklığı O(n) olarak hesaplanır.

Döngüler(Loops)

Döngüler, bir kod bloğunu belirli bir koşul dahilinde tekrar tekrar çalıştıran ifadelere denir. Döngü bloğunun çalıştırdığı her ifade ayrı ayrı hesaplanarak tekrar sayısı ile çarpılır. Bu durumda ayrı olarak çalışan her ifade için O(1), denilirse, n kez çalıştırma O(1) * n, bu da O(n) hesaplama karmaşıklığını oluşturur.

for I in 1 .. n loop
sequence of statements
end loop;

İç İçe Döngüler(Nested Loops)

İç içe döngüler, tekrar tekrar çalıştırılan bir kod bloğunu kapsayan bir döngünün, başka bir döngü ile yine tekrar tekrar çalıştırılmasına denir. Örneğin m ve n uzunluğuna sahip iki iç içe döngü, bir kod bloğunu n * m kez çalıştıracaktır. O(1) olarak çalışan bir kod bloğu, O(1) * n * m olacak şekilde, O(n * m) hesaplama karmaşıklığına sahiptir.

for I in 1 .. n loop
      for J in 1 .. m loop
      sequence of statements
   end loop;
end loop;

Fonksiyonlar(Functions)

Fonksiyonlar, prosedürler ve/veya metotlar, belirli isimler dahilinde kod bloklarını barındıran, çağrılabilir ve değer döndürebilir alt rutinlere verilen addır. Bu yapıların hesaplama karmaşıklığını, içerisinde barındırdığı kodların hesaplama karmaşıklığı oluşturur.

There has been no comment yet

Name:


Question/Comment
   Please verify the image




The Topics in Computer Science

Search this site for





 

Software & Algorithms

icon

In mathematics and computer science, an algorithm is a step-by-step procedure for calculations. Algorithms are used for calculation, data processing, and automated reasoning.

Programming Languages

icon

A programming language is a formal constructed language designed to communicate instructions to a machine, particularly a computer. It can be used to create programs to control the behavior of a machine. Java,C, C++,C#

Database

icon

A database is an organized collection of data. The data are typically organized to model aspects of reality in a way that supports processes requiring information.

Hardware

icon

Computer hardware is the collection of physical elements that constitutes a computer system. Computer hardware refers to the physical parts or components of a computer such as the monitor, memory, cpu.

Web Technologies

icon

Web development is a broad term for the work involved in developing a web site for the Internet or an intranet. Html,Css,JavaScript,ASP.Net,PHP are one of the most popular technologies. J2EE,Servlet, JSP,JSF, ASP

Mobile Technologies

icon

Mobile application development is the process by which application software is developed for low-power handheld devices, such as personal digital assistants, enterprise digital assistants or mobile phones. J2ME

Network

icon

A computer network or data network is a telecommunications network that allows computers to exchange data. In computer networks, networked computing devices pass data to each other along data connections.

Operating Systems

icon

An operating system is software that manages computer hardware and software resources and provides common services for computer programs. The OS is an essential component of the system software in a computer system. Linux,Windows

Computer Science

icon

Computer science is the scientific and practical approach to computation and its applications.A computer scientist specializes in the theory of computation and the design of computational systems.