Definició
Complexitat espacial (espai complexitat) és un algorisme de funcionament mesura d'ocupació temporal de la mida d'espai d'emmagatzematge, denotat per S (n) = O (f (n)). Com ara l'ordenació per inserció directa és temps de complexitat O (n ^ 2), la complexitat espacial és O (1). I no hi ha d'haver un algorisme recursiu O (n) la complexitat general d'espai, ja que cada informació de la declaració recursiva per ser emmagatzemat. Principals avantatges i desavantatges d'un algorisme de temps d'execució de l'algorisme i l'espai d'emmagatzematge necessari per mesurar dos aspectes.
Complexitat espacial
Similar a la complexitat de temps de la discussió, la complexitat espai d'un algorisme (SpaceComplexity) S (n) es defineix com l'espai d'emmagatzematge aritmètica que consumeix, sinó que també és una funció de la mida del problema n. Complexitat espai asimptòtica es coneix com la complexitat espai sovint. Complexitat espacial (SpaceComplexity) és un algoritme de funcionament mesura d'ocupació temporal de la mida d'espai d'emmagatzematge. Un algorisme en una memòria d'ordinador ocupat per l'espai d'emmagatzematge, incloent l'algorisme d'emmagatzematge en si l'espai d'emmagatzematge, l'entrada i sortida de l'algorisme d'espai d'emmagatzematge de dades i algoritmes durant l'operació d'espai d'emmagatzematge temporal ocupat per aquestes tres zones. Algorisme d'entrada i de sortida d'espai d'emmagatzematge de dades ocupada pel problema a ser resolt és determinat per la llista de paràmetres de la funció aprovada per l'anomenada ve amb aquest algorisme és que no varia. Algorisme d'emmagatzematge propi espai d'emmagatzematge proporcional a la longitud de l'escriptura i algorismes per comprimir aquest espai d'emmagatzematge, ha d'escriure una breu algorisme. Algorismes durant el funcionament l'espai d'emmagatzematge temporal varia amb l'algoritme, i alguns algoritmes necessiten només ocupen una petita quantitat d'unitat de treball temporal, i no varia amb la mida del problema i el canvi, anomenem aquest algorisme és un "\ locals" porta a terme, és per salvar els algoritmes d'emmagatzematge, tal com es descriu en aquesta secció tingut diversos algoritmes són tan; Alguns algorismes requereixen que el nombre d'unitats ocupades pel treball temporal i resoldre problemes relacionats amb la grandària de n, augmenta amb l'augment de n gran, quan n és gran, es trigarà més unitats d'emmagatzematge, com es descriu en el Capítol 9 ordenament ràpid i combinar algoritme d'ordenació és un exemple d'això.Anàlisi d'un espai d'emmagatzematge algorisme per a tots els aspectes considerats. Quant al algorisme recursiu, en general és relativament breu, el mateix algoritme ocupa menys espai d'emmagatzematge, però requereix una pila de temps d'execució addicional, que ocupen unitat de treball més temporal, si escrit en l'algorisme no recursiu pot típicament ser relativament llarg, propi algorisme més espai d'emmagatzematge, però el temps d'execució és probable que requereixi menys unitat d'emmagatzematge.
Espai complexitat d'un algorisme considerat només durant el funcionament per a les variables locals assignats mida de l'espai d'emmagatzematge, que inclou la llista de variables de paràmetres de paràmetres s'assignen espai d'emmagatzematge i es defineix en el cos de les variables locals de funció assignats espai d'emmagatzematge de dos parts. Si un algorisme és algoritme recursiu, i la seva complexitat espai és l'espai de pila recursiva utilitzat per la grandària, és igual a la primera trucada l'espai d'emmagatzematge temporal assignat multiplicat pel nombre de trucades (que és el nombre de crides recursives més 1, aquest 1 indica una trucada començarà no recursiva). Complexitat espacial de l'algorisme també es dóna generalment en la forma d'un ordre de magnitud. Per exemple, quan un algoritme de complexitat espai és una constant que no canvia amb la quantitat de dades processades N és la mida del canvi, es pot expressar com S (1); Quan un algoritme de complexitat i l'espai a la base 2 logarítmica n proporcional al temps, es pot expressar com O (log2), quan una divisió puc buidar la complexitat algorisme és linealment proporcional a n, es pot expressar com O (n) Si el paràmetre és una matriu, només cal assignar-li a. Emmagatzematge dels arguments enviats a la direcció d'un punter a l'espai, un espai de paraula de la màquina, i si un paràmetre com a mètodes de referència, només ha d'assignar un espai d'emmagatzematge electrònic, l'utilitzen per emmagatzemar la direcció de l'argument corresponent variables de manera que el sistema de referència automàticament per la variable d'argument.
Temps i espai comparació complexitat
Per a un algorisme la complexitat i complexitat espai-temps són sovint interdependents. Quan la recerca d'una major complexitat de temps, pot causar un rendiment deficient complexitat espacial, que pot conduir a ocupar més espai d'emmagatzematge, per contra, quan la recerca d'una major complexitat en espai, pot fer que la complexitat del temps el grau de deteriorament, el que pot conduir a prendre un temps d'execució llarg. A més, tot l'algorisme més o menys hi ha entre el rendiment de cada un. Per tant, quan es dissenya un algorisme (algorisme especialment gran), per a l'actuació tenint en compte l'algoritme, l'algoritme usant la freqüència, l'algorisme de la mida de les dades tractades, les característiques del llenguatge de descripció de l'algorisme, l'entorn dels sistemes de màquina que executa l'algorisme, etc factors a ser capaç de dissenyar un algoritme millor. Algorisme de complexitat de temps i la complexitat espai coneixen col · lectivament complexitat de l'algorisme.
|
